About Binary Search
Binary search is a divide-and-conquer algorithm that finds a target value in a sorted array. At each step, it compares the target with the middle element and eliminates half of the remaining search space. This gives it O(log n) time complexity — dramatically faster than linear search for large arrays. Binary search is one of the most fundamental algorithms in computer science and appears everywhere from database indexing to debugging (git bisect).
Complexity Analysis
- Time Complexity
- O(log n)
- Space Complexity
- O(1)
- Difficulty
- beginner
Key Concepts
Divide and Conquer
Binary search works by repeatedly dividing the search interval in half. If the target is less than the middle element, narrow to the left half. If greater, narrow to the right half.
Sorted Input Requirement
Binary search only works on sorted arrays. If the input is unsorted, the algorithm may miss the target entirely. Always verify the array is sorted before applying binary search.
Logarithmic Time Complexity
Each comparison eliminates half the remaining elements. For an array of n elements, this means at most ⌈log₂(n)⌉ comparisons. For 1 million elements, that's at most 20 comparisons — compared to 1 million for linear search.
Integer Overflow in Mid Calculation
The classic formula mid = (left + right) / 2 can overflow for very large arrays. A safer alternative is mid = left + (right - left) / 2. In JavaScript with 64-bit floats this isn't an issue for arrays up to 2⁵³, but it matters in languages with 32-bit integers like Java or C.
Common Pitfalls
Off-by-one in boundaries
The most common binary search bug is using < instead of <= in the while condition, or forgetting the +1 / -1 when updating left and right. These cause the algorithm to miss elements or loop infinitely.
Unsorted input
Binary search silently produces wrong results on unsorted arrays. It won't crash — it'll just return an incorrect answer. Always validate that input is sorted.
Empty array
An empty array should return -1 immediately. The loop condition left <= right handles this correctly (0 <= -1 is false), but it's worth testing explicitly.