Given a sorted data sequence, if the data sequence is empty, return
NULL to indicate the value does not exist, otherwise compare the
middle element's value with the value be…ing searched. If there's a
match, return a reference to that element. If there is no match and
the value being searched is smaller, repeat the search upon the
lower half of the sequence, otherwise repeat the search on the
upper half of the sequence.
The data sequence must be in sorted order. With each unsuccessful
iteration of the algorithm, the order allows us to eliminate half
of the remaining elements. Typically, the data sequence will be
implemented as an array (or vector) as this allows constant-time
random-access to the middle element of the sequence. A binary tree
can also be used but, for efficiency, the tree must be balanced.
That is, for any subtree within the tree, there must be the same
number of nodes under both the left and right branches or no more
than 1 node difference. With a balanced binary tree, every node is
the middle element of its subtree. Thus, for every unsuccessful
iteration, we simply traverse left or right, starting at the root.
The best case time complexity for binary search of n elements is
O(1), where the element is found in the first iteration (and is
therefore the middle element). The worst case is O(log n) - the
binary logarithm of n. (MORE)