Wikipedia: History of Binary search

Difference (from prior major revision) (minor diff, author diff)

Changed: 5,7c5

Input is a list L and a value V. L[x] denotes the xth element in L, which consists of N values, L[1], L[2], ..., L[N]. L[x] <= L[x+1], for all list elements between 1 and N-1.

Return success if at least one of the elements of L is equal to V, otherwise return failure

This sample Ruby implementation returns true if at least one of the elements of array is equal to value, otherwise return false

Changed: 9,26c7,21

function binary-search(L,V)
set start = 1
set end = N
repeat while start <= end
set middle = (start + end) div 2
if V = L[middle]
return success
else-if V < L[middle]
set end = middle - 1
else-if (V > L[middle])
set start = middle + 1
end-if
end-repeat
return failure
end-function

Notes:
div is integer division (discard any remainder)

def binary_search(array,value)
     first=0
     last=array.size - 1
     while (first <= last)
         mid = (first + last) / 2
 	if (value > array[mid])
 	    first = mid + 1
 	elsif (value < array[mid])
 	    last = mid - 1
 	else
 	    return true
 	end
     end
     return false
 end

	Revision 13 . . (edit) December 13, 2001 4:31 am by Hannes Hirzel
	Revision 12 . . (edit) December 13, 2001 4:31 am by Hannes Hirzel
	Revision 11 . . December 12, 2001 8:02 am by Taw [ruby implementation]
	Revision 10 . . (edit) September 27, 2001 10:01 pm by Dze27