## Binary Search

Searching for X in L.

**Linear search:** O(N)

Better way if L is sorted:

- Compare X to the middle value (M) in L.
- if X = M we are done.
- if X < M we continue searching in 1st half of L only.
- if X > M we continue searching in 2nd half of L only.

**Example:**
L = 1 3 4 6 8 9 11. X = 4.

- X < 6: Repeat with L = 1 3 4.
- X > 3: Repeat with L = 4.
- X = 4: We found X!

This is binary search: each iteration halves the length of the
list. Therefore, total number of iteration <= logN.

Difference between O(logN) and O(N) is very significant for large
N. N = 2 billion, linear search: 1 billion comparisons, binary search:
32 comparisons.