Binary Search
Efficiently find an element in a sorted array by repeatedly dividing the search interval in half.
What is Binary Search?
Binary Search is a foundational algorithm for finding a target value within a sorted array. It works by repeatedly comparing the target to the middle element of the array.
The Motivation: Dictionary Search
Imagine finding a word in a dictionary. You don't read every word from the start (Linear Search). Instead, you open the book to the middle. If the target word is alphabetically after the middle, you discard the first half and search the second half. You repeat this until you find the word.
Attempt 1: Linear Search (Brute Force)
The simplest way is to check every element from left to right.
function search(nums: number[], target: number): number {
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) return i;
}
return -1;
}
Why it fails
- Time Complexity: O(n). If the array has 1 billion elements, you might make 1 billion comparisons.
- Inefficient: It ignores the fact that the array is sorted.
The Intuition: Divide and Conquer
Since the array is sorted, we can rule out half of the elements in one step.
- Pick the middle element.
- If
middle === target, we are done. - If
middle < target, the target must be in the right half (every element to its left is smaller). - If
middle > target, the target must be in the left half. - Repeat on the smaller subarray.
Interactive Walkthrough
TARGET 9
READY
L
0
1
2
3
4
R
5
Left
0
Mid
—
Right
5
Result
—
Search the whole array for 9: left = 0, right = 5
Next
mid = 0 + (5 - 0) / 2 = 2, and nums[2] = 3
Array
Target
Legend & Complexity
nums[mid], the element being compared with the target
The target, once found
Outside [left, right]: ruled out (struck through)
Time
O(log n)
Extra space
O(1)
Step through the algorithm to see how the search range shrinks.
Dry Run Table
Dry Run: Target = 9
Array: [-1, 0, 3, 5, 9, 12]
| Step | Low | High | Mid | Value | Comparison | Action |
|---|---|---|---|---|---|---|
| 1 | 0 | 5 | 2 | 3 | 3 < 9 | Target is right. Low = 3 (Mid+1) |
| 2 | 3 | 5 | 4 | 9 | 9 == 9 | Found! |
The Solution Template
Standard Binary Search implementation.
Binary Search Code
1/**2 * @param {number[]} nums3 * @param {number} target4 * @return {number}5 */6var search = function(nums, target) {7 let left = 0;8 let right = nums.length - 1;910 while (left <= right) {11 // Prevent potential integer overflow compared to (left + right) / 212 let mid = Math.floor(left + (right - left) / 2);1314 if (nums[mid] === target) {15 return mid;16 } else if (nums[mid] < target) {17 left = mid + 1;18 } else {19 right = mid - 1;20 }21 }2223 return -1;24};
Edge Cases
- Empty array: Should return -1 immediately.
- Target not found: Loop completes, return -1.
- Single element: Start/Mid/End are all same index.
- Integer Overflow: Using
mid = (left + right) / 2can overflow in languages like C++/Java if left+right > 2^31. Usemid = left + (right-left)/2.
Summary
Binary Search reduces the search space by half at every step, achieving O(log n) efficiency. Standard on sorted arrays.