AppleScript: binary search

asbs.applescript

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

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