Binary Search Algorithm

Binary search is a search algorithm that finds the position of a target value within a sorted array by repeatedly comparing the target to the array's middle element and discarding the half of the array that cannot contain it. Because each comparison eliminates half the remaining elements, the algorithm needs at most about the logarithm, base two, of the array's size in comparisons, far fewer than the linear scan a plain search over an unsorted list requires. An early refinement in the algorithm's own history is Hermann Bottenbruch's implementation, published in 1962, which removed an unnecessary equality check present in earlier versions and set the form most textbooks now teach. Binary search requires the array to already be sorted, which is the tradeoff against its speed: unsorted data must be sorted first, or searched by a slower linear method instead.