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.

```
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
```

Worst | Average | Best | |
---|---|---|---|

Time |
\(O(\log n)\) | \(O(\log n)\) | \(O(1)\) |

Space |
\(O(1)\) |