Binary Search

Efficiently find an element in a sorted array by repeatedly dividing the search interval in half.

15 min

Time: O(n)

Space: O(1)

Solve on LeetCode

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 helps 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 (all elements to left are simpler).
If middle > target, the target must be in the left half.
Repeat on the smaller subarray.

Interactive Walkthrough

Step 1 / 1

Initializing...

Custom Input

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.

1/**
2 * @param {number[]} nums
3 * @param {number} target
4 * @return {number}
5 */
6var search = function(nums, target) {
7    let left = 0;
8    let right = nums.length - 1;
9
10    while (left <= right) {
11        // Prevent potential integer overflow compared to (left + right) / 2
12        let mid = Math.floor(left + (right - left) / 2);
13
14        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    }
22
23    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) / 2 can overflow in languages like C++/Java if left+right > 2^31. Use mid = left + (right-left)/2.

Time & Space Analysis

Time: O(log n) - we cut the search space in half each time.
Space: O(1) - iterative approach uses constant extra space.

Summary

Binary Search reduces the search space by half at every step, achieving O(log n) efficiency. Standard on sorted arrays.

Previous Problem

Longest Valid Parentheses

Next Problem

Koko Eating Bananas