Introduction
Binary search is a fast algorithm for finding a target value in a sorted array. Instead of checking every element like linear search at , you repeatedly split the search space in half.
Here's the key insight: if the array is sorted, one comparison tells you which half contains your target. You eliminate of remaining elements each step.
This halving gives you time complexity. For an array of million elements, you need at most comparisons instead of million.
The Algorithm
You maintain two pointers: left and right, representing the current search range.
Calculate the middle index: mid = left + (right - left) / 2
Compare arr[mid] with your target:
- If equal, you found it
- If target is smaller, search the left half:
right = mid - 1 - If target is larger, search the right half:
left = mid + 1
Repeat until left > right (target not found)
Visualize it as a decision tree. Each node is a comparison. You follow one branch and discard the other. The tree height is , so that's your worst-case comparisons.
Implementation
Here's the classic binary search:
function binarySearch(arr, target):
left = 0
right = arr.length - 1
while left <= right:
mid = left + (right - left) / 2
if arr[mid] == target:
return mid
else if arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
I use left + (right - left) / 2 instead of (left + right) / 2 to prevent integer overflow when left and right are large.
The condition left <= right ensures you check single-element ranges. If you use left < right, you might miss the target when it's the only element left.
Common Pitfalls
Off-by-one errors: Should you set right = mid or right = mid - 1? It depends on your loop condition. With left <= right, use mid - 1 and mid + 1 to avoid infinite loops.
Infinite loops: If left = mid when left + 1 == right, you loop forever. Always ensure your boundaries move.
Wrong return value: When the target doesn't exist, left points to where it would be inserted. This is useful for lower bound searches.
Debugging tip: Print left, right, and mid each iteration. Watch for boundaries that stop moving.