Write an algorithm with analysis steps for binary search?

Answer 1

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 being 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.