Binary Search | Phase 3

The Binary Search Template

Binary search halves the search space each iteration. The tricky part is getting boundary conditions right. Here are the two canonical templates:

C++
// TEMPLATE 1: Find exact target (or -1 if not found)
int binarySearch(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size()-1;
    while (lo <= hi) {
        int mid = lo + (hi-lo)/2;  // avoids integer overflow
        if      (nums[mid] == target) return mid;
        else if (nums[mid] <  target) lo = mid+1;
        else                          hi = mid-1;
    }
    return -1;
}

// TEMPLATE 2: Find leftmost position where condition is true
// "Find minimum X such that f(X) is true" (monotonic condition)
// lo converges to the answer
int binarySearchLeft(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size();
    while (lo < hi) {
        int mid = lo + (hi-lo)/2;
        if (nums[mid] < target) lo = mid+1;  // target is right
        else                    hi = mid;       // mid could be answer
    }
    return lo;  // first position where nums[pos] >= target
}

// STL equivalents (use these in interviews for speed)
lower_bound(v.begin(), v.end(), x); // first pos where val >= x
upper_bound(v.begin(), v.end(), x); // first pos where val >  x
binary_search(v.begin(), v.end(), x); // true if x exists
    

Binary Search on Answer

The most powerful application: binary search on the answer space rather than the array. Key insight: if we can check "is X a valid answer?" efficiently, we can binary search on X.

C++
// Pattern: "Find minimum/maximum X such that condition(X) is true/false"
// 1. Define a monotonic condition function
// 2. Binary search on the answer space [lo, hi]
// 3. Each check is O(n), total O(n log(answer_range))

// Example: Capacity to Ship Packages (LC 1011)
bool canShip(vector<int>& weights, int days, int cap) {
    int d=1, cur=0;
    for (int w : weights) {
        if (cur+w > cap) { d++; cur=0; }
        cur += w;
    }
    return d <= days;
}
int shipWithinDays(vector<int>& w, int days) {
    int lo = *max_element(w.begin(),w.end());  // min possible capacity
    int hi = accumulate(w.begin(),w.end(),0);  // max possible capacity
    while (lo < hi) {
        int mid = lo+(hi-lo)/2;
        if (canShip(w,days,mid)) hi=mid;
        else lo=mid+1;
    }
    return lo;
}
    

Interactive: Binary Search Trace

Searching for target = 7 in sorted array [1, 3, 5, 7, 9, 11, 13]. Watch lo/hi pointers close in on the answer.

Practice Problems

#704Binary SearchEasy

Search for target in a sorted array. Return index, or -1 if not found.

Pattern: Classic binary search. lo ≤ hi, mid = lo + (hi-lo)/2 to avoid overflow.

C++
int search(vector<int>& nums, int t) {
    int lo=0, hi=nums.size()-1;
    while(lo<=hi) {
        int m=lo+(hi-lo)/2;
        if     (nums[m]==t) return m;
        else if(nums[m]<t)  lo=m+1;
        else                hi=m-1;
    }
    return -1;
}
// Time: O(log n)  Space: O(1)

#33Search in Rotated Sorted ArrayMedium

A sorted array was rotated at some pivot. Find target in O(log n).

Pattern: At each mid, one half is always sorted. Check which half, then determine if target is in the sorted half → shrink to that half. Otherwise, shrink to the other half.

C++
int search(vector<int>& nums, int t) {
    int lo=0, hi=nums.size()-1;
    while(lo<=hi) {
        int m=lo+(hi-lo)/2;
        if(nums[m]==t) return m;
        if(nums[lo]<=nums[m]) {  // left half sorted
            if(t>=nums[lo]&&t<nums[m]) hi=m-1;
            else lo=m+1;
        } else {                  // right half sorted
            if(t>nums[m]&&t<=nums[hi]) lo=m+1;
            else hi=m-1;
        }
    }
    return -1;
}
// Time: O(log n)  Space: O(1)

#153Find Minimum in Rotated Sorted ArrayMedium

Find the minimum element in a rotated sorted array (no duplicates).

Pattern: If mid > hi, min is in right half (rotation is in right). Otherwise min is in left half (or is mid). Never cut mid from search.

C++
int findMin(vector<int>& nums) {
    int lo=0, hi=nums.size()-1;
    while(lo<hi) {
        int m=lo+(hi-lo)/2;
        if(nums[m]>nums[hi]) lo=m+1;  // min in right
        else                 hi=m;       // mid could be min
    }
    return nums[lo];
}
// Time: O(log n)  Space: O(1)

#74Search a 2D MatrixMedium

m×n matrix where each row and first element of each row is sorted. Search for target in O(log(m*n)).

Pattern: Treat as flattened 1D sorted array. Map mid index: row = mid/n, col = mid%n.

C++
bool searchMatrix(vector<vector<int>>& mat, int t) {
    int m=mat.size(), n=mat[0].size();
    int lo=0, hi=m*n-1;
    while(lo<=hi) {
        int mid=lo+(hi-lo)/2;
        int val=mat[mid/n][mid%n];
        if     (val==t) return true;
        else if(val<t)  lo=mid+1;
        else            hi=mid-1;
    }
    return false;
}
// Time: O(log(m*n))  Space: O(1)

#875Koko Eating BananasMedium

Find minimum eating speed k such that Koko can eat all piles within h hours. Each hour she eats from one pile at speed k.

Pattern: Binary search on answer (speed). Check if speed k is feasible in O(n). Search range: [1, max(piles)].

C++
int minEatingSpeed(vector<int>& piles, int h) {
    int lo=1, hi=*max_element(piles.begin(),piles.end());
    while(lo<hi) {
        int mid=lo+(hi-lo)/2;
        long hrs=0;
        for(int p:piles) hrs+=(p+mid-1)/mid;  // ceil(p/mid)
        if(hrs<=h) hi=mid;     // feasible, try slower
        else       lo=mid+1;  // too slow, eat faster
    }
    return lo;
}
// Time: O(n log(max_pile))  Space: O(1)

#4Median of Two Sorted ArraysHard

Find the median of two sorted arrays. Must be O(log(m+n)).

Pattern: Binary search on partition of smaller array. Partition both arrays so left half has (m+n)/2 elements. Adjust until max(left) ≤ min(right).

C++
double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
    if(A.size()>B.size()) swap(A,B);  // A is smaller
    int m=A.size(), n=B.size();
    int lo=0, hi=m;
    while(lo<=hi) {
        int i=lo+(hi-lo)/2, j=(m+n+1)/2-i;
        int Al = (i>0 ? A[i-1] : INT_MIN);
        int Ar = (i<m ? A[i]   : INT_MAX);
        int Bl = (j>0 ? B[j-1] : INT_MIN);
        int Br = (j<n ? B[j]   : INT_MAX);
        if(Al<=Br && Bl<=Ar) {
            if((m+n)%2) return max(Al,Bl);
            return (max(Al,Bl)+min(Ar,Br))/2.0;
        } else if(Al>Br) hi=i-1;
        else lo=i+1;
    }
    return 0;
}
// Time: O(log(min(m,n)))  Space: O(1)

#35Search Insert PositionEasy

Given sorted array and target, return index if found, else return index where it would be inserted.

Pattern: Binary search leftmost variant. lo=0, hi=n. Run standard binary search — at end, lo is the insertion point.

C++
int searchInsert(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[mid]<target) lo=mid+1;
        else hi=mid-1;
    }
    return lo;  // lo = insertion point when not found
}
// Time: O(log n)  Space: O(1)

#162Find Peak ElementMedium

A peak element is greater than its neighbors. Find any peak index. Must be O(log n).

Pattern: Binary search on monotonicity. If nums[mid] < nums[mid+1], the right side must contain a peak. Otherwise the left side does.

C++
int findPeakElement(vector<int>& nums) {
    int lo=0, hi=nums.size()-1;
    while(lo<hi) {
        int mid=lo+(hi-lo)/2;
        if(nums[mid]<nums[mid+1]) lo=mid+1;  // climb right slope
        else                       hi=mid;      // mid or left has peak
    }
    return lo;
}
// Time: O(log n)  Space: O(1)

Binary Search on Answer: Whenever you see "find minimum X that satisfies Y" or "find maximum X that satisfies Y", and Y can be checked in O(n) — binary search on X. This unlocks a class of hard problems.

Deeper Understanding

Why Binary Search Is More Than Arrays

The Three Search Space Types

When to Use Binary Search

Array is sorted (or rotated sorted)

Direct binary search on indices. For rotated array: check which half is sorted, then determine which half target is in.

"Find minimum X such that condition(X) is true"

Binary search on the answer space. Condition must be monotonic: once it becomes true, stays true. Check feasibility in O(n).

2D matrix where rows and columns are sorted

Map to 1D index: mid/n gives row, mid%n gives col. Run standard binary search on flattened view.

Need leftmost or rightmost occurrence

Use the "lo converges" variant: when found, don't return — set hi=mid (left) or lo=mid+1 (right) to keep searching.

Find peak in unimodal function / bitonic array

Climb the slope: if mid < mid+1, move right; else move left. Guaranteed to converge to a peak in O(log n).

Common Misconceptions

"Binary search only works on sorted arrays"

Wrong. Binary search works on any monotonic condition — sorted value spaces, feasibility checks, peak finding — even on unsorted value ranges.

"lo + (hi - lo) / 2 is the same as (lo + hi) / 2"

Not in C++. (lo + hi) overflows when both are large ints. Always use lo + (hi - lo) / 2 to be safe.

"The loop condition lo < hi vs lo <= hi doesn't matter"

Wrong. lo <= hi is for finding an exact value. lo < hi is for converging on leftmost/rightmost. Off-by-one errors here cause infinite loops.

Follow-Up Problems to Push Deeper

#34 Find First and Last Position (Medium)

Two binary searches: leftmost and rightmost occurrence. Good practice for the lo-converges variant.

#1011 Capacity to Ship Packages (Medium)

Binary search on answer: minimum ship capacity that ships all packages in D days. Classic feasibility check pattern.

#1283 Find the Smallest Divisor (Medium)

Binary search on divisor value with a threshold check. Identical pattern to Koko Eating Bananas — practice the template.