previous | start | next

## Binary Search

- Binary search is a O(log n) algorithm.
- Suppose n = 100, after each search the size of the search range is cut in half to 50, 15, 12, 6, 3, and 1.
  - After seven comparisons we are done.
  - log2100 is about 6.64386
  - 27 = 128.
- Since binary search is so much faster, is it worthwhile to always sort data before searching?
  - An O(n) search is less work that a O(n log n) sort, so it's not worth it if you only have to perform one search.
  - Sorting first might be worth it if you perform a number of searches of the same vector.

previous | start | next