binary search, can it be doine in applescript

Scripting Forums AppleScript | Mac OS X
#1

I have a script that at the moment checks a filename against excel rows.

It gets the filename and then scans column 1 to see if that filename exist if it does ten it moves the file.

Quite simple really. But…

The excel sheet is sort alphabetically and uses letters. What i would like to do is do a binary search as this would be alot quicker.

For those who dont know a binary search goes half way through the list it then sees if the value you have is either higher or lower than the current item. If higher then it goes to the next half, which would be the 3rd quarter mark. Does the same search. It stops when it reaches a point where the current item is equal to the search string.

Example, using numbers:

5 < looking for 5 in a list of 1 - 20
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20

On first step:
get half way point 10.

Is 5 < current item if yes get next point (half of 10)
Is 5 = current item, yes then there is the search co,mplete.

As you can see this is alot faster, only 2 checks and not 5.

Does anyone know how to do this??? Baring in mind i use an excel sheet, but i would be able to put it in a text document sorted if that would be easier.

#2

Yes, this is the fastest algorithm, but I’m sure that this search algorithm is built into both AppleScript and VBA of Excel. So, you probably should not come up with your own algorithm.

You shouldn’t even compare the speed, because your algorithm will be in the AppleScript language, and the built-in search will be in lower-level languages.

#3

Whether or not a binary search is faster than a linear one depends on where the item is in the list. :slight_smile: For instance, if the item turns out to be one of the first three in a twenty-item list, a binary search will need four checks to find it. But binary does tend to be faster generally. It’s quite easy to write such a search in AS — in fact I’ve just written this from scratch (and memory) rather than try to locate the one I wrote years ago. If the list contains multiple instances of the item, the index returned is that of the first:

on binarySearch(orderedList, searchItem)
	if (orderedList contains searchItem) then
		script o
			property lst : orderedList
		end script
		
		set l to 1
		set r to (count orderedList)
		repeat while (l < r)
			set m to (l + r) div 2
			if (item m of o's lst < searchItem) then
				set l to m + 1
			else
				set r to m
			end if
		end repeat
		return l
	else
		return 0
	end if
end binarySearch

set orderedList to {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
set searchItem to 13
binarySearch(orderedList, searchItem)

Since the OP posted his question sixteen years ago (you really should stop replying to obsolete threads — its creating a hell of a lot of noise on this site), it’s become possible to use ASObjC methods which don’t require the list to be ordered, although these will often carry a small time overhead because of the need to convert the list and search object to ASObjC equivalents:

use AppleScript version "2.4" -- 10.10 or later.
use framework "Foundation"
use scripting additions

on listSearch(theList, searchItem)
	set arrayEquivalent to current application's class "NSArray"'s arrayWithArray:(theList)
	if ((arrayEquivalent's containsObject:(searchItem)) as boolean) then
		return (arrayEquivalent's indexOfObject:(searchItem)) + 1
	else
		return 0
	end if
end listSearch

set orderedList to {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
set searchItem to 13
listSearch(orderedList, searchItem)