Sorting and Searching

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.
- log₂100 is about 6.64386
- 2⁷ = 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.