Skip to content

Instantly share code, notes, and snippets.

@mk2
Last active March 27, 2023 22:32
Show Gist options
  • Save mk2/9949533 to your computer and use it in GitHub Desktop.
Save mk2/9949533 to your computer and use it in GitHub Desktop.
AppleScript: binary search
use scripting additions
set AppleScript's text item delimiters to {", "}
--
-- バイナリサーチ
--
on binarySearch:aValue withValues:values
set res to false
set valuesLength to count values
set midIndex to valuesLength div 2
-- item 0 of を実行するとエラーになるので、ここでリターン
if midIndex = 0 then
if aValue = (first item of values) then
set res to true
end if
return res
end if
set midValue to item midIndex of values
log "value is " & values
log "values length is " & valuesLength
log "mid index is " & midIndex
log "mid vlaue is " & midValue
if midValue > aValue then
set res to (my binarySearch:aValue withValues:(items 1 thru midIndex of values))
else if midValue < aValue then
set res to (my binarySearch:aValue withValues:(items (midIndex + 1) thru valuesLength of values))
else if midValue = aValue then
set res to true
end if
return res
end binarySearch:withValues:
--
-- バイナリサーチテスト
--
set values to {1, 2, 3, 6, 7, 9, 11, 13, 15}
repeat with i from 1 to (end of values)
set searchValue to i
log "Search for " & i
set result to (my binarySearch:searchValue withValues:values)
if result then
log "The search value[" & searchValue & "] is found in " & values & "."
else
log searchValue & " not found."
end if
end repeat
@walterrowe
Copy link

walterrowe commented Mar 27, 2023

Thanks for sharing this. I modified your binary search to always use the complete values list and call itself recursively with different lower and upper indexes. It returns the index of the found item or 0 if not found.

-- @param	aValue		The value to find
-- @param	values		The full values list to search
-- @param	iLower		The lower index (intially 1)
-- @param	iUpper		The upper index (initially count of values)
-- @returns	0 or index	Return 0 for not found, index when found

on binarySearch(aValue, values, iLower, iUpper)
	
	set valueIndex to 0
	set midIndex to (iLower + ((iUpper - iLower) div 2))
	
	-- if search list is narrowed down to only 1 item
	if (iUpper - iLower)  2 then
		if aValue = (item iLower of values) then
			set valueIndex to iLower
		end if
		if aValue = (item iUpper of values) then
			set valueIndex to iUpper
		end if
		return valueIndex
	end if
	
	set midIndex to (iLower + ((iUpper - iLower) div 2))
	set midValue to item midIndex of values

	if midValue = aValue then
		return midIndex
	else if midValue > aValue then
		return my binarySearch(aValue, values, iLower, midIndex)
	else if midValue < aValue then
		return my binarySearch(aValue, values, (midIndex + 1), iUpper)
	end if
	
end binarySearch

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment