Binary Search

Searching for X in L.

Linear search: O(N)

Better way if L is sorted:

1. Compare X to the middle value (M) in L.
2. if X = M we are done.
3. if X < M we continue searching in 1st half of L only.
4. 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.