Binary Search

The pattern: Repeatedly halve the search space by checking a midpoint condition. If the condition is met, search one half; otherwise, search the other. Each step eliminates 50% of possibilities.

Why this matters in interviews: Binary search appears everywhere — sorted arrays, answer-space problems, rotated arrays, matrix search. It reduces O(n) linear scans to O(log n). Interviewers love it because the idea is simple but getting the boundary conditions right is tricky.

When to Recognize It

• The input is sorted (or has a monotonic property)
• You’re searching for a specific value or the boundary where a condition flips
• The problem asks for “minimum X such that…” or “maximum X such that…” (binary search on answer)
• Keywords: “sorted,” “rotated sorted,” “minimum speed,” “maximum days,” “find peak”
• The brute force is O(n) and you need O(log n)

How It Works

Imagine a phone book with 1000 pages. To find “Smith,” you open to the middle — page 500. If “Smith” comes after page 500 alphabetically, you ignore the first half and search pages 501-1000. Next, you check page 750. Each step cuts the remaining pages in half. After ~10 steps, you’ve found it.

flowchart TD
    A["Search space: 1 to n"]:::client
    B{"Check mid"}:::service
    C["Left half"]:::data
    D["Right half"]:::data
    E["Found or boundary"]:::client

    A --> B
    B -->|"condition true"| C
    B -->|"condition false"| D
    C --> B
    D --> B
    B -->|"lo meets hi"| E

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

The key invariant: At every step, the answer is always within [lo, hi]. We never exclude the half that might contain the answer.

Template Code

Code

def binary_search(nums, target):
    """Standard binary search for exact match."""
    lo, hi = 0, len(nums) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return -1  # not found

int binarySearch(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int binarySearch(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

function binarySearch(nums, target) {
    let lo = 0, hi = nums.length - 1;

    while (lo <= hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (nums[mid] === target) return mid;
        else if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Variations

Binary Search on Answer

When the problem asks “what’s the minimum/maximum value X such that some condition is satisfiable?” — you binary search on X itself, not on an array index.

Code

def binary_search_on_answer(lo, hi):
    """Find minimum value where condition is True."""
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if condition(mid):  # can we do it with 'mid'?
            hi = mid        # try smaller
        else:
            lo = mid + 1    # need bigger

    return lo  # minimum valid answer

int searchOnAnswer(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (condition(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

int searchOnAnswer(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (condition(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

function searchOnAnswer(lo, hi) {
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (condition(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Example: Koko eating bananas — binary search on the eating speed. For each speed, check if she can finish all bananas in H hours.

Search in Rotated Sorted Array

A sorted array rotated at some pivot. One half is always sorted. Check which half is sorted, then decide if the target lies in that sorted half.

Code

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid

        # Left half is sorted
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1

    return -1

int searchRotated(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

int searchRotated(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

function searchRotated(nums, target) {
    let lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (nums[mid] === target) return mid;
        if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

Find Minimum in Rotated Sorted Array

Binary search for the pivot point — the minimum is where the sorted order breaks.

Complexity

Common Mistakes

• Integer overflow in mid calculation — use lo + (hi - lo) / 2 instead of (lo + hi) / 2
• Wrong loop condition — lo <= hi for exact match, lo < hi for boundary search. Mixing them up causes infinite loops or missed answers
• Off-by-one in boundary updates — when using lo < hi, set hi = mid (not mid - 1) to avoid skipping the answer
• Not identifying which half is sorted in rotated arrays — always check nums[lo] <= nums[mid] first

Practice Problems

• Binary Search
• Search in Rotated Sorted Array
• Koko Eating Bananas
• Find Minimum in Rotated Sorted Array
• Search a 2D Matrix

Key Takeaways

• Binary search works on any monotonic condition, not just sorted arrays
• “Binary search on answer” is the most powerful variant — works whenever you can verify a candidate answer in O(n) or less
• For rotated arrays, one half is always sorted — use that to decide which half to search
• Get the template right (loop condition + boundary updates) and the rest is just plugging in the condition