Binary search for closest match

Scripting Forums Code Exchange
#1

Hello.

I guess there is such a handler somewhere in here, but I haven’t found it. It is a binary search algorithm, tweaked to return the closest match of a number. The table it looks for data in must be sorted, ascending.

It requires the abs function of Satimage.Osax.

property vernalEquinoxIdx : {¬
	1700.0, ¬
	1800.0, ¬
	1900.0, ¬
	1950.0, ¬
	2000.0, ¬
	2100.0, ¬
	2200.0}

# set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, 1500)
# set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, 1958)
# set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, 2300)
set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, 2000)

		on binarySearchForClosestMatch(theList, value)
		local l, r, m, decreasing, probe, diff, diff2, oldL
		script o
			property lst : theList
		end script
		set {l, r, decreasing, probe} to {1, (count theList), false, 1.0E+16} # Big number
		
		repeat while true
			set m to (l + r) div 2
			set {diff, diff2} to {abs (value - (item l of o's lst)), abs ((item m of o's lst) - value)}
			# Changed operations, thanks to Bazzie Wazzie.
			if diff2 < diff then
				set {diff, l} to {diff2, m + 1}
			else
				set r to m - 1
			end if
			
			if diff < probe then
				if diff2 = diff then
					set oldL to m
				else
					set oldL to l
				end if
				set {decreasing, probe} to {true, diff}
			else if decreasing then
				return oldL
			end if
		end repeat
	end binarySearchForClosestMatch
#2

For the non-satimage users like me:

property vernalEquinoxIdx : {1700, 1800, 1900, 1950, 2000, 2100, 2200, 2300, 2400, 2500}

set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, 1500)
set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, 1976)
set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, 2100)
set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, 1300)

on binarySearchForClosestMatch(theList, theKey)
	script o
		property lst : theList
	end script
	
	set l to 1
	set r to (count o's lst)
	
	repeat
		set m to (l + r) div 2
		set mv to item m of o's lst
		
		if mv = theKey then
			return m
		else if r - l = 1 then
			set d1 to theKey - (item l of o's lst)
			set d2 to (item r of o's lst) - theKey
			if d1 > d2 then
				return r
			else
				return l
			end if
		else if mv > theKey then
			set r to m
		else
			set l to m
		end if
	end repeat
end binarySearchForClosestMatch
#3

Hello.

It looks very nice, and it is sure faster, but won’t work as well with negative numbers, which is why I put the abs handler there. now, in order for it to work with negative numbers,I believe you could use your handler, and reverse the list to descending order. :slight_smile:

In all fairness, I didn’t specify that it was to work with negative numbers as well in my initial post, but then again, I wanted it to simply just work. However, I didn’t perform the differences like you did, with value - item l and item m - value, and thatd didn’t work well, when passing zero. Thanks!

It should now pick the negative value, if both a negative and positive value generates the same difference, (size of interval between the two numbers). The list is sorted ascending, so any negative numbers turns up first in the list.

The binary search principle is useful for many thing, amongst other, the only bullet proof way to iterate a solution to an equation, because binary search, doesn’t make you have to find the inflection points for the equation, and such, that you’ll have to do if you use Newton Raphson, Picard, or Regula Falsi.

I made this handler to pick a central value to construct a table around when performing interpolation.

#4

thanks!

It does work with negative numbers as long as the list is ordered correctly from low to high. I’ve tested that before posting even knowing you didn’t mention it :slight_smile:

edit:


property vernalEquinoxIdx : {-2500, -2400, -2300, 0, 100, 250}

set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, -2600)
set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, -2401)
set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, -2100)
set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, -1)
#5

Hello.

My initial case was a key with a value of −2, a value at place l of −3 and a value 1 at m. I fumbled when I placed the elements, I placed the element −3 below 1, as that was the natural way for me to order it.

Now that I have arranged it the way it should, your version works out perfectly! With no abs function. :slight_smile:

Sorry about the miss.

But they still work a little bit differently, (so I have something for all the overhead), and that is, that my version breaks out the second, the size of the difference increases, whereas yours doesn’t return before the interval of keys is 1.

I’ll think I’ll steal yours, and rework it, to return faster. :slight_smile:

#6

Hi.

Here’s another variation. It’s written so that, when the list contains a run of items with the same value, it’s always the index of the first one which is returned (if it matches the key!). Otherwise the performance doesn’t seem to be very different from that of DJ’s script:

property vernalEquinoxIdx : {1700, 1800, 1900, 1950, 2000, 2100, 2200, 2300, 2400, 2500, 2500}

set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, 1500)
set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, 1976)
set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, 2100)
set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, 1300)

on binarySearchForClosestMatch(theList, theKey)
	script o
		property lst : theList
	end script
	
	set l to 1
	set r to (count theList)
	
	repeat while (r > l + 1)
		set m to (l + r) div 2
		
		if (item m of o's lst < theKey) then
			set l to m
		else
			set r to m
		end if
	end repeat
	
	if (theKey - (item l of o's lst) > (item r of o's lst) - theKey) then
		return r
	else
		return l
	end if
end binarySearchForClosestMatch
#7

Hello.

Ok, so it seems like short-circuiting the algorithm, instead of waiting for r = l +1 was a bad idea anyway.

Nigel just demonstrated that, in spades, with the perfect solution. :slight_smile: Having said that; DJ Bazzie Wazzies method works, mine didn’t turn out to work correctly in all cases.

Nigels method returns the correct result, with the same amount of iterations. To trie to reduce the number of iterations further, leads to unpredictable results, and even more overhead… :slight_smile:

The properties of a list that are sorting descended, combined with the binary search are such that you will indeed find the correct closest match with the shortest number of steps. If you try to make it converge faster, then you may miss the correct value indeed.

I started out, by converting a sequential search for finding closest match into a binary search, and I didn’t inspect the properties of the whole well enough.

Thanks to both of you for contributing.

#8

First, thanks to everyone for the idea, and Nigel separately for the best script. I think it can be improved by making it universal. There is an unpleasant limitation. The user must provide only a pre-ordered list of numbers.

The principle of the proposed improvement is simple - the user provides any list of numbers, and the script organizes it himself. I do not know if binary sorting can again be used for this. If so, then I myself do not understand this. Maybe someone will provide a similar script. Or, quick AppleScriptObjC sorting if this will be faster than binary sorting with plain Applescript.

Other idea is this: the user provides to handler multiple numbers (for which the user wants to find a match, and the script results in a list of matching numbers).

Passed to main handler list should have isSorted property (true, false) to avoid sorting again when it is sorted already.


set myNumbers to {1750, 1300, 100, 19.5, 2000, 11, 2200, 2800, 14, 3543, 354}
set vernalEquinoxIdx to {1700, 1800, 1900, 1950, 2000, 2100, 2200, 2300, 2400, 2500, 2500}
set isSorted to true

set matches to binarySearchForClosestMatch(vernalEquinoxIdx, isSorted, myNumbers)

The last if block is better to return the values instead of indexes:


set itemR to item r of o's lst
set itemL to item l of o's lst
if (theKey - itemL > itemR - theKey) then
		return itemR
	else
		return itemL
	end if

The script by Nigel Garvey I called “Binary Search for the closest number from an ordered list”. A new script I would call “Binary search for the closest numbers from the list”.

#9

Well. As a quick patch, using my Custom Iterative Ternary Merge Sort handler:

use sorter : script "Custom Iterative Ternary Merge Sort"

property vernalEquinoxIdx : {2300, 1900, 2000, 2200, 1950, 2400, 2500, 1700, 2100, 1800, 2500}

set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, 2500)
set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, 1976)
set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, 2100)
set mtch to binarySearchForClosestMatch(vernalEquinoxIdx, 1300)

on binarySearchForClosestMatch(theList, theKey)
	script o
		property lst : theList's items -- A new list containing the same items as theList, for sorting.
		property indices : {}
	end script
	
	-- Make a list of indices.
	repeat with i from 1 to (count theList)
		set end of o's indices to i
	end repeat
	-- Sort the copy of the original list, rearranging the index list in parallel with it.
	tell sorter to sort(o's lst, 1, -1, {slave:{o's indices}})
	
	-- Find the nearest match in the sorted list.
	set l to 1
	set r to (count theList)
	
	repeat while (r > l + 1)
		set m to (l + r) div 2
		
		if (item m of o's lst < theKey) then
			set l to m
		else
			set r to m
		end if
	end repeat
	
	-- Return the appropriate index from the index list.
	if (theKey - (item l of o's lst) > (item r of o's lst) - theKey) then
		return item r of o's indices
	else
		return item l of o's indices
	end if
end binarySearchForClosestMatch

I’ll think about it some more when I get back from my shopping expedition ….

#10

Thanks, for me it is all what is needed! I will modify my other preferences for myself.

#11

Hi KniazidisR.

It occurred to me while I was out that sorting a list of indices isn’t actually necessary. You can can identify the item you want using the sorted copy of the main list and then (if you actually want its index) search for it in the original list.

#12

Here’s a version which doesn’t use a sort at all:

property vernalEquinoxIdx : {2300, 1900, 2000, 2200, 1950, 2400, 2500, 1700, 2100, 1800, 2500}

set mtch to searchForClosestMatch(vernalEquinoxIdx, 2500)
set mtch to searchForClosestMatch(vernalEquinoxIdx, 1976)
set mtch to searchForClosestMatch(vernalEquinoxIdx, 2100)
set mtch to searchForClosestMatch(vernalEquinoxIdx, 1300)

on searchForClosestMatch(theList, theKey)
	script o
		property lst : theList's items
	end script
	
	set nearestLower to missing value	
	set nearestHigher to missing value
	set l to missing value
	set h to missing value
	
	repeat with i from 1 to (count theList)
		set v to item i of o's lst
		if (v is theKey) then
			return i
		else if (v > theKey) then
			if ((nearestHigher is missing value) or (v < nearestHigher)) then
				set nearestHigher to v
				set h to i
			end if
		else if ((nearestLower is missing value) or (v > nearestLower)) then
			set nearestLower to v
			set l to i
		end if
	end repeat
	
	if ((l is missing value) or (h is missing value)) then
		return {l, h}'s first integer
	else if (theKey - nearestLower > nearestHigher - theKey) then
		return h
	else
		return l
	end if
end searchForClosestMatch
#13

Thank you, but I like your first script more. I will continue to use it.

I already found a simple binary sorter for a list of numbers (I don’t know who created it) and wrote universal code for myself. For those who are interested in universal code, I bring it here:


global isSorted

set myNumbers to {1750, 1300, 100, 19.5, 2000, 11, 2200, 2800, 14, 3543, 354}
set vernalEquinoxIdx to {2300, 1900, 2000, 155, 1950, 131, 2500, 1700, 2100, 13, 2500}
set isSorted to false

set aResultingList to my sortListandPerformBinarySearchForClosestMatch(myNumbers, vernalEquinoxIdx)

on sortListandPerformBinarySearchForClosestMatch(theNumbers, vernalEquinoxIdx)
	if not isSorted then my quick_sort(vernalEquinoxIdx, 1, count of vernalEquinoxIdx)
	set result_List to {}
	repeat with aNumber in theNumbers
		set result_List to result_List & my binarySearchForClosestMatch(vernalEquinoxIdx, aNumber)
	end repeat
	return result_List
end sortListandPerformBinarySearchForClosestMatch

on binarySearchForClosestMatch(theList, theKey)
	script o
		property lst : theList
	end script
	
	set l to 1
	set r to (count theList)
	
	repeat while (r > l + 1)
		set m to (l + r) div 2
		
		if (item m of o's lst < theKey) then
			set l to m
		else
			set r to m
		end if
	end repeat
	
	if (theKey - (item l of o's lst) > (item r of o's lst) - theKey) then
		return item r of o's lst
	else
		return item l of o's lst
	end if
end binarySearchForClosestMatch

on quick_sort(a, l, r)
	--this sorts the list in place, no need to return anything
	local i, j, v
	script o
		property p : a
	end script
	set {i, j} to {l, r}
	set v to o's p's item ((l + r) div 2)
	repeat while (j > i)
		repeat while (o's p's item i < v)
			set i to i + 1
		end repeat
		repeat while (o's p's item j > v)
			set j to j - 1
		end repeat
		if (not i > j) then
			set o_s_p_s_item_i to o's p's item i
			set o's p's item i to o's p's item j
			set o's p's item j to o_s_p_s_item_i
			set {i, j} to {i + 1, j - 1}
		end if
	end repeat
	if (l < j) then quick_sort(o's p, l, j)
	if (r > i) then quick_sort(o's p, i, r)
	set isSorted to true
end quick_sort
#14

OK. The scripts in posts #9 and #12 return the indices of the numbers in the unsorted list. Yours sorts the list and returns the indices after sorting, which is presumably what you actually wanted.

(You probably don’t mean or need ‘set theList to’ in the sortListandPerformBinarySearchForClosestMatch() handler.)

#15

The Quicksort algorithm is by S.A.R. (Tony) Hoare and dates from around 1959. The AppleScript implementation of it in your script (except for the line which sets your isSorted global) was posted to the AppleScript-Users mailing list by Arthur J. Knapp in July 2002. (I thought I recognised the style!). Unfortunately, his post hasn’t survived in Apple’s own archive of the forum. (Actually, his July 2002 post explicitly replaces the settings of variable by list with individual settings, so maybe your version was earlier than that.) The following year, we collaborated off-list on some ideas he had for making it faster — which led to my own interest in sorting algorithms and the various AppleScript sort implementations I’ve posted here over the years. :slight_smile:

Like many of the people who used to contribute to the AppleScript fora back then, Arthur no longer seems to have a presence on the Internet. :frowning:

#16

Indeed, no need. I updated my script. Thanks again.