Binary search

Binary search is a Search algorithm suitable for searching a set of sorted data for a particular value.

In its most simple form, binary search takes a sorted list of data, and a value to be searched for. It returns success if the value is found in the data, and failure if the value is not found in the data.

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

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

Binary search executes in O(log n). Specifically, 1 + log₂ N iterations are needed to return an answer. It can be implemented using recursion or iteration?, although in many languages it is more elegantly expressed recursively.

An example of binary search in action is a simple guessing game in which a player has to guess a positive integer selected by another player between 1 and N, using only questions answered with yes or no. Supposing N is 16 and the number 11 is selected, the game might proceed as follows.

Is the number greater than 8? (Yes)
Is the number greater than 12? (No)
Is the number greater than 10? (Yes)
Is the number greater than 11? (No)

Therefore, the number must be 11. At most ceiling(log₂ N) questions are required to determine the number, since each question halves the search space. Note that one less question (iteration) is required than for the general algorithm, since the number is constrained to a particular range.

/Talk