Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › DSA

Binary Search

Binary search finds a target in a sorted array by looking at the middle and throwing away the half that can't contain it. Each step halves the search space, so it takes O(log n) time — about 30 steps for a billion elements.

The basic version

int binarySearch(vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;       // avoids overflow of (lo + hi)
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;  // target is on the right
        else hi = mid - 1;                  // target is on the left
    }
    return -1;                              // not found
}

Iterative: O(log n) time, O(1) space. A recursive version uses O(log n) stack.

Why lo + (hi - lo) / 2?

(lo + hi) can overflow when both are near 2³¹. In Python it doesn't matter, but use the safe form in C++/Java.

Lower bound and upper bound (the most useful template)

int lowerBound(vector<int>& a, int x) {
    int lo = 0, hi = a.size();             // answer is in [lo, hi]; hi = size means "none"
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] >= x) hi = mid;         // mid might be the answer — keep it
        else lo = mid + 1;
    }
    return lo;
}

Built-ins: C++ lower_bound(a.begin(), a.end(), x), Python bisect_left(a, x) / bisect_right, Java Collections.binarySearch (returns any match).

Uses:

Search in a rotated sorted array

[4,5,6,7,0,1,2] — one half around mid is always sorted.

def search(a, t):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == t: return mid
        if a[lo] <= a[mid]:                  # left half is sorted
            if a[lo] <= t < a[mid]: hi = mid - 1
            else: lo = mid + 1
        else:                                # right half is sorted
            if a[mid] < t <= a[hi]: lo = mid + 1
            else: hi = mid - 1
    return -1

Find a peak element

A peak is bigger than its neighbours. If a[mid] < a[mid+1], a peak exists on the right; otherwise on the left (including mid). O(log n) even though the array isn't sorted.

Binary search on the answer

When the question is "find the minimum x such that condition(x) is true" and the condition is monotonic (false, false, …, true, true), binary search over x.

Example — Koko eating bananas: piles [3,6,7,11], 8 hours. What's the minimum eating speed?

def can_finish(piles, h, speed):
    return sum((p + speed - 1) // speed for p in piles) <= h   # ceil division

def min_speed(piles, h):
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_finish(piles, h, mid): hi = mid    # works — try slower
        else: lo = mid + 1                        # too slow
    return lo

Answer: 4. Complexity: O(n log max).

Same pattern: ship packages within D days, allocate books (minimise the maximum pages), aggressive cows (maximise the minimum distance — search for the largest x where the condition holds), square root of n.

Square root without sqrt()

Find the largest x with x·x ≤ n: binary search on x in [0, n] (use long for x·x).

Binary search on 2-D matrices

If each row is sorted and the first element of a row is greater than the last of the previous one, treat it as one sorted array of size r·c: index k → (k / c, k % c).

How to avoid infinite loops

Loop Update rules Ends with
while (lo <= hi) lo = mid + 1, hi = mid - 1 lo > hi
while (lo < hi), mid rounds down hi = mid and lo = mid + 1 lo == hi
while (lo < hi), need lo = mid use mid = lo + (hi - lo + 1) / 2 (round up) lo == hi

Test your code on arrays of size 0, 1 and 2 — that's where the bugs hide.

Complexity summary

Problem Time
search / lower bound O(log n)
rotated array, peak O(log n)
binary search on answer O(log(range) × cost of the check)

Practice

Binary Search problems. Classic list: Binary Search, First and Last Position, Search Insert Position, Rotated Sorted Array, Find Minimum in Rotated Array, Peak Element, Koko Eating Bananas, Capacity to Ship Packages, Median of Two Sorted Arrays.

Interview one-liners

More DSA notes