Questions
31 of 59
What is the precondition for Binary Search?
Difficulty: 1/10
Binary Search Preconditions
The fundamental precondition is that the search space must have an ordering that allows half of the candidates to be safely discarded after each comparison. For the standard array implementation, this means the data must be sorted according to the same ordering used by the comparison.
javascript
- 1
Data must be sorted or otherwise monotonically ordered.
- 2
The comparison must be consistent with that ordering.
- 3
Random access is important for efficient array-based binary search.
- 4
Time complexity is O(log n).
Follow-up Questions
- What happens if the array is unsorted?
- How do you find the first occurrence using binary search?