Binary Search: Template, Lower Bound and Rotated Arrays

Looking up a word in a printed dictionary, nobody reads from page one. You open it near the middle, see that your word comes later, and never look at the first half again. Binary search is that habit made exact: in a sorted array, compare the target with the middle element, keep the half that could still contain it, and repeat. It is famous for being easy to get subtly wrong, so this lesson gives you one template and the reason for each of its lines.

Why a linear scan is too slow

A scan is O(n) per search. With n = 10⁶ sorted prices and q = 10⁵ queries that is up to 10¹¹ steps, a thousand times what a judge allows in a second. It wastes the one fact that matters: in a sorted array, one comparison tells you about every element on one side of it.

The idea: halve the range every step

Keep two indices, lo and hi, around the part of the array where the target could still be. In this lesson the range is inclusive: both a[lo] and a[hi] are candidates. Look at the middle element:

• nums[mid] equals the target: found.
• nums[mid] is less than the target: everything up to mid is too small, so lo = mid + 1.
• nums[mid] is greater than the target: everything from mid on is too big, so hi = mid - 1.

Stop when the range is empty, lo > hi: the target is not there.

1. The array is sorted, so if 8 is anywhere it lies between lo and hi, which start at the two ends. Each step looks at the middle and throws away the half that cannot hold it.
2. mid = (0 + 8) / 2 = 4 and nums[4] = 16 is more than 8. Everything from index 4 on is at least 16, so the target can only be to the left.
3. hi moves to mid − 1 = 3, so 5 numbers leave the search in one step; 4 numbers remain between lo and hi.
4. mid = (0 + 3) / 2 = 1, rounded down, and nums[1] = 5 is less than 8. Everything up to index 1 is at most 5, so the target can only be to the right.
5. lo moves to mid + 1 = 2, discarding 2 numbers at once; 2 numbers remain between lo and hi.
6. mid = (2 + 3) / 2 = 2, rounded down, and nums[2] = 8: found at index 2 after 3 comparisons. Halving the range each time needs at most 4 looks for 9 numbers: O(log n), where a scan could need 9.

Why it works: the invariant

One sentence stays true on every pass of the loop: if the target is in the array, its index is between lo and hi. It is true at the start, when the range is the whole array, and each update keeps it true, because an update only removes elements that sorted order has proved cannot be the target. The loop also ends: both updates drop mid itself, so the range loses at least one element every pass. When it is empty, the invariant says the target lies in an empty range — so it is absent.

1. The invariant: if 20 is in the array, its index is between lo and hi. It starts true because lo and hi are the two ends. The dashed line is the target's height; sorted bars climb past it exactly once.
2. mid = 4 holds 16, under the line. The bars are sorted, so every bar from index 0 to 4 is at most 16 — all under the line too. None can be the target, so lo jumps to 5 and the invariant still holds.
3. mid = 6 holds 38, over the line, and so does every bar after it. Those 3 bars are discarded: hi = mid − 1 = 5. Each step drops mid itself as well, so the range always shrinks.
4. mid = 5 holds 23, over the line, and so does every bar after it. That bar is discarded: hi = mid − 1 = 4. Each step drops mid itself as well, so the range always shrinks.
5. lo has passed hi: the range is empty. The invariant says 20, if present, lies in that empty range — so it is absent, proved after 3 looks instead of 9. A range that shrinks every step must end.

In an interview, be ready to say it out loud: what is the invariant, and why does the range shrink?

One template you can trust

Most binary search bugs come from mixing conventions. This lesson uses one form everywhere:

lo = 0, hi = n - 1             # inclusive: lo..hi are the candidates
ans = n                        # what to return if nothing qualifies
while lo <= hi:                # the range is not empty
    mid = lo + (hi - lo) / 2   # rounded down
    if condition(mid):         # mid qualifies
        ans = mid              # remember it ...
        hi = mid - 1           # ... and look for an earlier one
    else:
        lo = mid + 1           # mid and everything before it fail
return ans

It finds the first index where a condition becomes true, for any condition that is false for a while and then true to the end. "The value is at least the target" is one such condition; "this capacity is enough", in the next lesson, is another. Each line has a reason:

• while (lo <= hi): when lo == hi, one candidate is left and still needs checking.
• mid + 1 and mid - 1, never mid: dropping mid is what makes the range shrink. hi = mid inside this loop can leave a one-element range unchanged, and the loop spins for ever.
• ans remembers the best index so far, because a qualifying mid may not be the first. At the end ans equals lo.
• lo + (hi - lo) / 2: in C++ and Java, lo + hi overflows once both pass about 1.07 billion — a bug Java's own library carried for nine years until 2006. In JavaScript, wrap the division in Math.floor.

The other popular template — hi = n, while (lo < hi), hi = mid — is also correct; it is the C++ standard library's [first, last) convention. The danger is only in mixing the two.

1. Ask of every index: is nums[i] ≥ 3? On a sorted array the answers run no, no, …, then yes to the end. The lower bound is the first yes. The search reads the answer only at mid — the rest stay unknown.
2. mid = 3: nums[3] = 3 ≥ 3, a yes. It might not be the first yes, so remember it as ans = 3 and keep looking to the left: hi = 2.
3. mid = 1: nums[1] = 3 ≥ 3, a yes. It might not be the first yes, so remember it as ans = 1 and keep looking to the left: hi = 0.
4. mid = 0: nums[0] = 1 < 3, a no — and so is everything before it. lo = mid + 1 = 1.
5. The range is empty with lo = 1, hi = 0, and ans = 1: the first 3 is at index 1, found with 3 looks among 8. Change ≥ to > and the same loop finds the upper bound.

Lower bound, upper bound and the first and last occurrence

Two boundaries answer almost every question about a value in a sorted array: the lower bound, the first index with nums[i] >= target, and the upper bound, the first with nums[i] > target. Only the condition changes; the loop does not.

1. Lower bound is the first yes to ≥ 3, upper bound the first yes to > 3. Every copy of 3 sits between them, so first = lower, last = upper − 1 and the count is upper − lower: two O(log n) searches, however many copies.
2. For 4, which is absent, the two rows agree: both bounds are 4, the slot where 4 would have to be inserted to keep the array sorted. That is Search Insert Position.

The code

The program prints the first and last position and the count for values that are present, and the insert position for values that are not.

#include <iostream>
#include <vector>
using namespace std;

// First index i with a[i] >= target, or n when there is none.
// The live range is lo..hi with both ends included.
int lowerBound(const vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    int ans = (int)a.size();             // the answer if no value is big enough
    while (lo <= hi) {                   // the range lo..hi is not empty
        int mid = lo + (hi - lo) / 2;    // the middle, without overflowing
        if (a[mid] >= target) {
            ans = mid;                   // mid qualifies; look for an earlier one
            hi = mid - 1;
        } else {
            lo = mid + 1;                // mid and everything before it are too small
        }
    }
    return ans;
}

// First index i with a[i] > target, or n when there is none.
int upperBound(const vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    int ans = (int)a.size();
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] > target) {           // the only change: > instead of >=
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    return ans;
}

int main() {
    vector<int> nums = {1, 3, 3, 3, 5, 8, 8, 10};
    cout << "nums:";
    for (int x : nums) cout << " " << x;
    cout << "\n";
    for (int target : {3, 8, 4, 0, 11}) {
        int first = lowerBound(nums, target);
        int last = upperBound(nums, target) - 1;
        if (first < (int)nums.size() && nums[first] == target) {
            cout << "target " << target << ": first " << first << ", last " << last
                 << ", count " << last - first + 1 << "\n";
        } else {
            cout << "target " << target << ": absent, insert at " << first << "\n";
        }
    }
    return 0;
}

public class Main {
    // First index i with a[i] >= target, or n when there is none.
    // The live range is lo..hi with both ends included.
    static int lowerBound(int[] a, int target) {
        int lo = 0, hi = a.length - 1;
        int ans = a.length;                  // the answer if no value is big enough
        while (lo <= hi) {                   // the range lo..hi is not empty
            int mid = lo + (hi - lo) / 2;    // the middle, without overflowing
            if (a[mid] >= target) {
                ans = mid;                   // mid qualifies; look for an earlier one
                hi = mid - 1;
            } else {
                lo = mid + 1;                // mid and everything before it are too small
            }
        }
        return ans;
    }

    // First index i with a[i] > target, or n when there is none.
    static int upperBound(int[] a, int target) {
        int lo = 0, hi = a.length - 1;
        int ans = a.length;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] > target) {           // the only change: > instead of >=
                ans = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 3, 3, 5, 8, 8, 10};
        StringBuilder line = new StringBuilder("nums:");
        for (int x : nums) line.append(" ").append(x);
        System.out.println(line);
        for (int target : new int[] {3, 8, 4, 0, 11}) {
            int first = lowerBound(nums, target);
            int last = upperBound(nums, target) - 1;
            if (first < nums.length && nums[first] == target) {
                System.out.println("target " + target + ": first " + first + ", last " + last
                        + ", count " + (last - first + 1));
            } else {
                System.out.println("target " + target + ": absent, insert at " + first);
            }
        }
    }
}

def lower_bound(a, target):
    """First index i with a[i] >= target, or len(a) when there is none.
    The live range is lo..hi with both ends included."""
    lo, hi = 0, len(a) - 1
    ans = len(a)                     # the answer if no value is big enough
    while lo <= hi:                  # the range lo..hi is not empty
        mid = lo + (hi - lo) // 2    # the middle (Python ints never overflow)
        if a[mid] >= target:
            ans = mid                # mid qualifies; look for an earlier one
            hi = mid - 1
        else:
            lo = mid + 1             # mid and everything before it are too small
    return ans


def upper_bound(a, target):
    """First index i with a[i] > target, or len(a) when there is none."""
    lo, hi = 0, len(a) - 1
    ans = len(a)
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] > target:          # the only change: > instead of >=
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return ans


nums = [1, 3, 3, 3, 5, 8, 8, 10]
print("nums:", *nums)
for target in (3, 8, 4, 0, 11):
    first = lower_bound(nums, target)
    last = upper_bound(nums, target) - 1
    if first < len(nums) and nums[first] == target:
        print(f"target {target}: first {first}, last {last}, count {last - first + 1}")
    else:
        print(f"target {target}: absent, insert at {first}")

// First index i with a[i] >= target, or a.length when there is none.
// The live range is lo..hi with both ends included.
function lowerBound(a, target) {
  let lo = 0;
  let hi = a.length - 1;
  let ans = a.length; // the answer if no value is big enough
  while (lo <= hi) {
    // the range lo..hi is not empty
    const mid = lo + Math.floor((hi - lo) / 2); // the middle, rounded down
    if (a[mid] >= target) {
      ans = mid; // mid qualifies; look for an earlier one
      hi = mid - 1;
    } else {
      lo = mid + 1; // mid and everything before it are too small
    }
  }
  return ans;
}

// First index i with a[i] > target, or a.length when there is none.
function upperBound(a, target) {
  let lo = 0;
  let hi = a.length - 1;
  let ans = a.length;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] > target) {
      // the only change: > instead of >=
      ans = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  return ans;
}

const nums = [1, 3, 3, 3, 5, 8, 8, 10];
console.log(`nums: ${nums.join(" ")}`);
for (const target of [3, 8, 4, 0, 11]) {
  const first = lowerBound(nums, target);
  const last = upperBound(nums, target) - 1;
  if (first < nums.length && nums[first] === target) {
    console.log(`target ${target}: first ${first}, last ${last}, count ${last - first + 1}`);
  } else {
    console.log(`target ${target}: absent, insert at ${first}`);
  }
}

nums: 1 3 3 3 5 8 8 10
target 3: first 1, last 3, count 3
target 8: first 5, last 6, count 2
target 4: absent, insert at 4
target 0: absent, insert at 0
target 11: absent, insert at 8

Check first < n before reading nums[first]: when every value is smaller than the target, the lower bound is one past the end. The same program solves Find First and Last Position of Element in Sorted Array, and Binary Search is a lower bound plus one equality check.

Search in a rotated sorted array

A rotated sorted array is a sorted array cut at some point with the two pieces swapped: [0, 1, 2, 4, 5, 6, 7] becomes [4, 5, 6, 7, 0, 1, 2]. One fact survives: cut it anywhere, and at least one side is sorted. If nums[lo] <= nums[mid], lo..mid has no drop in it; otherwise mid..hi is the sorted side, and a sorted side tells you exactly whether it holds the target.

1. A sorted array cut and swapped: two climbing ramps with one drop between them. The whole array is not sorted, but cut it anywhere and at least one side of the cut has no drop in it — that side is sorted.
2. mid = 3 holds 7. nums[lo] = 4 ≤ 7, so lo..mid is the sorted side and holds exactly the values 4 to 7. 0 is not inside, so search right: lo = 4.
3. mid = 5 holds 1. nums[lo] = 0 ≤ 1, so lo..mid is the sorted side and holds exactly the values 0 to 1. 0 is inside, so search left: hi = 4.
4. mid = 4 holds 0: found at index 4 in 3 looks. Each look discarded half the range, so a rotated array still costs O(log n).

Finding the minimum, where the rotation happened, is the template with a different condition: with distinct values, "nums[i] <= nums[n - 1]" is false on the left ramp and true on the right one.

#include <iostream>
#include <vector>
using namespace std;

// Index of the smallest value in a rotated sorted array of distinct values:
// the first index whose value is <= the last value.
int findMinIndex(const vector<int>& a) {
    int lo = 0, hi = (int)a.size() - 1;
    int ans = hi;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= a.back()) {        // mid is in the lower, rotated-in part
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;                // mid is in the upper part: minimum is right of it
        }
    }
    return ans;
}

// Index of target in a rotated sorted array of distinct values, or -1.
int searchRotated(const vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[lo] <= a[mid]) {                                 // lo..mid is sorted
            if (a[lo] <= target && target < a[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                                               // mid..hi is sorted
            if (a[mid] < target && target <= a[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

int main() {
    vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
    cout << "nums:";
    for (int x : nums) cout << " " << x;
    cout << "\n";
    int m = findMinIndex(nums);
    cout << "minimum " << nums[m] << " at index " << m << "\n";
    for (int target : {0, 5, 3}) {
        int i = searchRotated(nums, target);
        if (i == -1) cout << "target " << target << ": not found\n";
        else cout << "target " << target << ": found at index " << i << "\n";
    }
    return 0;
}

public class Main {
    // Index of the smallest value in a rotated sorted array of distinct values:
    // the first index whose value is <= the last value.
    static int findMinIndex(int[] a) {
        int lo = 0, hi = a.length - 1;
        int ans = hi;
        int last = a[a.length - 1];
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] <= last) {            // mid is in the lower, rotated-in part
                ans = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;                // mid is in the upper part: minimum is right of it
            }
        }
        return ans;
    }

    // Index of target in a rotated sorted array of distinct values, or -1.
    static int searchRotated(int[] a, int target) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] == target) return mid;
            if (a[lo] <= a[mid]) {                                 // lo..mid is sorted
                if (a[lo] <= target && target < a[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else {                                               // mid..hi is sorted
                if (a[mid] < target && target <= a[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        StringBuilder line = new StringBuilder("nums:");
        for (int x : nums) line.append(" ").append(x);
        System.out.println(line);
        int m = findMinIndex(nums);
        System.out.println("minimum " + nums[m] + " at index " + m);
        for (int target : new int[] {0, 5, 3}) {
            int i = searchRotated(nums, target);
            if (i == -1) System.out.println("target " + target + ": not found");
            else System.out.println("target " + target + ": found at index " + i);
        }
    }
}

def find_min_index(a):
    """Index of the smallest value in a rotated sorted list of distinct values:
    the first index whose value is <= the last value."""
    lo, hi = 0, len(a) - 1
    ans = hi
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] <= a[-1]:          # mid is in the lower, rotated-in part
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1             # mid is in the upper part: minimum is right of it
    return ans


def search_rotated(a, target):
    """Index of target in a rotated sorted list of distinct values, or -1."""
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] == target:
            return mid
        if a[lo] <= a[mid]:                          # lo..mid is sorted
            if a[lo] <= target < a[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                        # mid..hi is sorted
            if a[mid] < target <= a[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1


nums = [4, 5, 6, 7, 0, 1, 2]
print("nums:", *nums)
m = find_min_index(nums)
print(f"minimum {nums[m]} at index {m}")
for target in (0, 5, 3):
    i = search_rotated(nums, target)
    if i == -1:
        print(f"target {target}: not found")
    else:
        print(f"target {target}: found at index {i}")

// Index of the smallest value in a rotated sorted array of distinct values:
// the first index whose value is <= the last value.
function findMinIndex(a) {
  let lo = 0;
  let hi = a.length - 1;
  let ans = hi;
  const last = a[a.length - 1];
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] <= last) {
      // mid is in the lower, rotated-in part
      ans = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1; // mid is in the upper part: minimum is right of it
    }
  }
  return ans;
}

// Index of target in a rotated sorted array of distinct values, or -1.
function searchRotated(a, target) {
  let lo = 0;
  let hi = a.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] === target) return mid;
    if (a[lo] <= a[mid]) {
      // lo..mid is sorted
      if (a[lo] <= target && target < a[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      // mid..hi is sorted
      if (a[mid] < target && target <= a[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

const nums = [4, 5, 6, 7, 0, 1, 2];
console.log(`nums: ${nums.join(" ")}`);
const m = findMinIndex(nums);
console.log(`minimum ${nums[m]} at index ${m}`);
for (const target of [0, 5, 3]) {
  const i = searchRotated(nums, target);
  if (i === -1) console.log(`target ${target}: not found`);
  else console.log(`target ${target}: found at index ${i}`);
}

nums: 4 5 6 7 0 1 2
minimum 0 at index 4
target 0: found at index 4
target 5: found at index 1
target 3: not found

These are Search in Rotated Sorted Array and Find Minimum in Rotated Sorted Array. Both need distinct values: with duplicates, nums[lo] == nums[mid] == nums[hi] hides the sorted half, and shrinking both ends by one makes the worst case O(n).

Other shapes of the same search

Once binary search means "find where a condition flips", it appears beyond sorted arrays:

• A sorted matrix, read row by row, is one sorted array: index k is cell (k / n, k % n). See Search a 2D Matrix and the matrix lesson.
• Letters: Find Smallest Letter Greater Than Target is an upper bound that wraps to the first letter.
• A peak: in Find Peak Element nothing is sorted, yet if nums[mid + 1] is larger, the climb to the right must end at a peak.
• The answer itself: "the smallest capacity that works" is searched over candidate answers — the next lesson, binary search on the answer.

The library versions

Java does not promise which copy it finds, so first-or-last questions need the template.

Time and space complexity

The price is the precondition: sorting costs O(n log n) (see sorting algorithms), so for one search on unsorted data a scan is cheaper. A hash set answers "is it present?" faster, but not "what is the first value at least x?".

How to recognise a binary search problem

• The input is sorted, and the question is about a value, a position or a count.
• The statement demands O(log n) time.
• It asks for the first or last position of something, or the smallest value at least some target.
• A yes-or-no question over a range of values switches exactly once — the sign that you can search the answer.

Common mistakes

• Mixing templates: hi = mid inside while (lo <= hi) never shrinks a one-element range.
• (lo + hi) / 2 with ints overflows past 2,147,483,647; in JavaScript an index of 3.5 reads undefined.
• Stopping at the first match when the question wants the first or last occurrence.
• Reading past the end: the lower bound can be n.
• Searching unsorted data, which returns wrong answers without any error.

Practice in this order

1. Binary Search: the exact-match search.
2. Search Insert Position: the lower bound and nothing else.
3. Find Smallest Letter Greater Than Target: an upper bound with a wrap-around.
4. Find First and Last Position of Element in Sorted Array: both bounds.
5. Search a 2D Matrix: one sorted array in disguise.
6. Find Peak Element: a condition you have to justify.
7. Find Minimum in Rotated Sorted Array: the template with an "at most the last value" condition.
8. Search in Rotated Sorted Array: the sorted-half argument.

The binary search problem list has every problem in the catalogue that uses the technique. Next, binary search on the answer, where the array disappears and you search the answer itself.