What must be true before you can use binary search on a list?
Options
- The list must have an even length
- The list must be sorted (Correct option)
- The list must contain only integers
- The list must be smaller than 1000
Answer
The list must be sorted
Why
Binary search decides which half to discard by comparing the target with the middle element. That only makes sense if smaller values are on the left and bigger values on the right, i.e. the list is sorted.
On an unsorted list it gives wrong answers. If you search many times, sorting once (O(n log n)) then searching (O(log n) each) can pay off.
Remember
Binary search needs sorted data.