logarithmicSearch
Moderators: FourthWorld, heatherlaine, Klaus, kevinmiller
logarithmicSearch
Hi,
I found this code on internet, but I doesn't find anything, it returns 0 to me:
########CODE to copy and paste#######
function logarithmicSearch @pArray pItem pLeft pRight
local tIndex
local tResult
# create a new range pointer that points to the item that lies
# right between the left and right range pointers
put round ((pLeft + pRight) / 2) into tIndex
# if we have found the matching item then stop processing and return it
if pArray[tIndex] = pItem then
put tIndex into tResult
# if any of the range pointers have the same value
# then the item we are looking for does not exist in the array and we return 0
else if (pLeft = pRight or pLeft = tIndex or pRight = tIndex) then
put 0 into tResult
# if we have not yet found a match and none of the range pointers have the same
# value then call logarithmicSearch again with a smaller search range
# we are effectively halving the search area, each time we call logarithmicSearch
else if pArray[tIndex] > pItem then
put logarithmicSearch (pArray, pItem, pLeft, tIndex) into tResult
else
put logarithmicSearch (pArray, pItem, tIndex, pRight) into tResult
end if
return tResult
end logarithmicSearch
#####END OF CODE generated by http://tinyurl.com/j8xf3xq with livecode 9.0.0-dp-1#####
What's wrong?
I found this code on internet, but I doesn't find anything, it returns 0 to me:
########CODE to copy and paste#######
function logarithmicSearch @pArray pItem pLeft pRight
local tIndex
local tResult
# create a new range pointer that points to the item that lies
# right between the left and right range pointers
put round ((pLeft + pRight) / 2) into tIndex
# if we have found the matching item then stop processing and return it
if pArray[tIndex] = pItem then
put tIndex into tResult
# if any of the range pointers have the same value
# then the item we are looking for does not exist in the array and we return 0
else if (pLeft = pRight or pLeft = tIndex or pRight = tIndex) then
put 0 into tResult
# if we have not yet found a match and none of the range pointers have the same
# value then call logarithmicSearch again with a smaller search range
# we are effectively halving the search area, each time we call logarithmicSearch
else if pArray[tIndex] > pItem then
put logarithmicSearch (pArray, pItem, pLeft, tIndex) into tResult
else
put logarithmicSearch (pArray, pItem, tIndex, pRight) into tResult
end if
return tResult
end logarithmicSearch
#####END OF CODE generated by http://tinyurl.com/j8xf3xq with livecode 9.0.0-dp-1#####
What's wrong?
Livecode Wiki: http://livecode.wikia.com
My blog: https://livecode-blogger.blogspot.com
To post code use this: http://tinyurl.com/ogp6d5w
My blog: https://livecode-blogger.blogspot.com
To post code use this: http://tinyurl.com/ogp6d5w
-
- VIP Livecode Opensource Backer
- Posts: 10050
- Joined: Sat Apr 08, 2006 7:05 am
- Contact:
Re: logarithmicSearch
No commas between params - does it even compile?
Richard Gaskin
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn
Re: logarithmicSearch
@Max
What Richard means is you have no data in which to fill your parameters. The function even calls for an array as one of them.
@Richard.
It does compile without commas. I did not think that was possible.
Craig
What Richard means is you have no data in which to fill your parameters. The function even calls for an array as one of them.
@Richard.
It does compile without commas. I did not think that was possible.
Craig
Re: logarithmicSearch
Hi Max,
the function is correct,
also with spaces instead of commas between params what is a legal definition**.
You found a LC lesson:
http://lessons.livecode.com/m/4071/l/11 ... h-an-array
What's wrong with that lesson is the call to the function.
An array tArray is filled with names. The example calls then
put logarithmicSearch (tSortedArray, "Best, Tony", 0, 15) -- wrong name of array.
This should read:
put logarithmicSearch (tArray, "Best, Tony", 0, 15) -- correct name of array.
With that correct call you get the correct result 3.
Hermann
________
** This is the function I used when testing this
the function is correct,
also with spaces instead of commas between params what is a legal definition**.
You found a LC lesson:
http://lessons.livecode.com/m/4071/l/11 ... h-an-array
What's wrong with that lesson is the call to the function.
An array tArray is filled with names. The example calls then
put logarithmicSearch (tSortedArray, "Best, Tony", 0, 15) -- wrong name of array.
This should read:
put logarithmicSearch (tArray, "Best, Tony", 0, 15) -- correct name of array.
With that correct call you get the correct result 3.
Hermann
________
** This is the function I used when testing this

Code: Select all
function I'm already here
return "You are" && already && here
end I'm
on mouseUp
answer I'm ("not yet","there")
end mouseUp
shiftLock happens
-
- VIP Livecode Opensource Backer
- Posts: 10050
- Joined: Sat Apr 08, 2006 7:05 am
- Contact:
Re: logarithmicSearch
Thanks. Never seen that before in any other LC examples, or any other language for that matter (including other xTalks).[-hh] wrote:the function is correct,
also with spaces instead of commas between params what is a legal definition**.
The anomaly of having commas optional is made more curious by allowing that in the definition only. When calling a handler, any arguments not separated by commas throw an error.
FWIW. a tip about passing by reference:
That function passes the first arg by reference, denoted with a preceding "@". This can be useful when any modifications being made to the data should affect the original data, rather than work on a copy.
Historically "@" was also sometimes used for performance/memory reasons, to reduce an unnecessary copy of large data, as seems to be the case with this function. But since around v7.x and later, that's no longer needed. LC now uses "copy on write" for argument data. All read operations in arg data are done on the original data.
If the receiving handler modifies the data, at that point the data is copied. Unless of course you've told it to always use the original data with "@".
So the efficiency sought here in this read-only handler by using "@" is no longer needed. Newer versions of LC provide that efficiency by default.
Richard Gaskin
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn
Re: logarithmicSearch
Yes. I simply didn't want to change the function given in the search-an-array lesson.
These lessons were written in a very clear style several years ago and may be now updated in the sense of your post.
These lessons were written in a very clear style several years ago and may be now updated in the sense of your post.
shiftLock happens
Re: logarithmicSearch
The problem is that logarthmic search looks for a sorted array. I thought that mine was sorted, but I was wrong.
This is the function to sort arrays:
This is the function to sort arrays:
Code: Select all
function sortedArray @pArray
# fetch the keys and sort them using the array entry values
get the keys of pArray
sort lines of it by pArray[each]
split it by return
# create a new sorted array using the mapped keys
put 1 into tNextIndex
repeat for each element tIndex in it
put pArray[tIndex] into tSortedArray[tNextIndex]
add 1 to tNextIndex
end repeat
return tSortedArray
end sortedArray
Livecode Wiki: http://livecode.wikia.com
My blog: https://livecode-blogger.blogspot.com
To post code use this: http://tinyurl.com/ogp6d5w
My blog: https://livecode-blogger.blogspot.com
To post code use this: http://tinyurl.com/ogp6d5w