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.

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.