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