home

Binary search

In a naive, or sequential search for some item in a list, each element must be visited. If however the list is sorted, a binary search may instead be used to recursively divide and conquer.

A binary search works over a sorted list of inputs. It compares against the middle element then recurses into either the left or right sub-lists as required, halving the search space with each iteration.

The structure of this style of search may also be modelled by a Binary search tree.

Algorithm

IF list is empty
RETURN unsuccesful
ELSE
x ← middle element
IF x = item
RETURN success (or item, or index)
ELSE IF x > item
recurse into left sublist
ELSE
recurse into right sublist

Performance

Worst Average Best
Time $$O(\log n)$$ $$O(\log n)$$ $$O(1)$$
Space $$O(1)$$