DSA · Lesson 5 of 17

Binary Search

⏱ 16 min🎬 Interactive visualizer💻 Python · Java · C++ · JavaScript🧩 6 practice problems

Halve the search space each step for O(log n). Works on sorted arrays and, more powerfully, on any monotonic yes/no question about the answer.

The idea

If the data is sorted, compare with the middle element and throw away the half that cannot contain the answer. A billion elements need only about 30 comparisons.

Three templates worth memorising

Exact match: while lo <= hi, return on equality.
Lower bound (first index with a[i] >= x): half-open range [lo, hi), while lo < hi, set hi = mid when a[mid] >= x. This gives insertion positions, first and last occurrences, and LIS in O(n log n).
Binary search on the answer: when “can we do it with value k?” is monotonic (false … false, true … true), binary-search the smallest k that works. Examples: Koko eating bananas, ship packages within D days, split array largest sum, minimum time to finish tasks.

Recognise it

Sorted input, or a sorted matrix
“Find the minimum / maximum value such that …”
Rotated sorted arrays (one half is always sorted)
Constraints such as values up to 10⁹, where checking every value is too slow but O(n log V) fits

Code template

# 1) Exact match
def search(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x: return mid
        if a[mid] < x: lo = mid + 1
        else: hi = mid - 1
    return -1

# 2) Lower bound: first index with a[i] >= x
def lower_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x: lo = mid + 1
        else: hi = mid
    return lo

# 3) Binary search on the answer
def smallest_ok(lo, hi, ok):        # ok(k) is False...False, True...True
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid): hi = mid
        else: lo = mid + 1
    return lo

// 1) Exact match
int search(int[] a, int x) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == x) return mid;
        if (a[mid] < x) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
}

// 2) Lower bound: first index with a[i] >= x
int lowerBound(int[] a, int x) {
    int lo = 0, hi = a.length;
    while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] < x) lo = mid + 1; else hi = mid; }
    return lo;
}

// 3) Binary search on the answer
int smallestOk(int lo, int hi, java.util.function.IntPredicate ok) {
    while (lo < hi) { int mid = lo + (hi - lo) / 2; if (ok.test(mid)) hi = mid; else lo = mid + 1; }
    return lo;
}

// 1) Exact match
int search(const vector<int>& a, int x) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == x) return mid;
        if (a[mid] < x) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
}

// 2) Lower bound: std::lower_bound does exactly this
int lowerBound(const vector<int>& a, int x) { return lower_bound(a.begin(), a.end(), x) - a.begin(); }

// 3) Binary search on the answer
template <class F> long long smallestOk(long long lo, long long hi, F ok) {
    while (lo < hi) { long long mid = lo + (hi - lo) / 2; if (ok(mid)) hi = mid; else lo = mid + 1; }
    return lo;
}

// 1) Exact match
function search(a, x) {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (a[mid] === x) return mid;
    if (a[mid] < x) lo = mid + 1; else hi = mid - 1;
  }
  return -1;
}

// 2) Lower bound: first index with a[i] >= x
function lowerBound(a, x) {
  let lo = 0, hi = a.length;
  while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] < x) lo = mid + 1; else hi = mid; }
  return lo;
}

// 3) Binary search on the answer
function smallestOk(lo, hi, ok) {
  while (lo < hi) { const mid = Math.floor((lo + hi) / 2); if (ok(mid)) hi = mid; else lo = mid + 1; }
  return lo;
}

Complexity

O(log n) for a search. Binary search on the answer is O(log V × cost of one feasibility check), often O(n log V).

Practise this pattern (6 problems)

Each problem has a statement, hints, approaches, solutions in 4 languages and a code runner. Solve them in order: easy first.

#	Problem	Difficulty
21	Binary Search	Easy
22	Search Insert Position	Easy
23	Find Minimum in Rotated Sorted Array	Medium
24	Search in Rotated Sorted Array	Medium
25	Koko Eating Bananas	Medium
26	Search a 2D Matrix	Medium

Common mistakes

mid = (lo + hi) / 2 overflow in Java/C++ for big values: use lo + (hi − lo) / 2.
Infinite loops: with while lo < hi, always shrink the range (lo = mid + 1 or hi = mid, never lo = mid).
Mixing inclusive [lo, hi] and half-open [lo, hi) styles in the same code.

Check yourself: what is the first value Koko’s speed search tries for piles [3, 6, 7, 11]?

lo = 1, hi = 11, so mid = 6. At speed 6 she needs 1 + 1 + 2 + 2 = 6 hours.

🧩 All DSA problems 🎬 Algorithm visualizer 🎓 Certificates

Created by Ajeetkumar