Iterative binary search templates

Why this matters

Binary search finds a position in a sorted list by looking at the middle and throwing away the half that cannot hold the answer. Lesson 01 of this module explains the idea. This lesson is about the loop: the exact lines that move the two ends of the search range, and the small choices that decide whether the loop stops with the right answer or never stops at all.

Most bugs in binary search are not bugs in the idea. They are off-by-one mistakes, a wrong loop condition, or an update that does not move the range forward. A good template removes those choices. You copy the shape that fits your question, and the shape already handles the edges.

This lesson gives three templates. Each one answers a different question. Lesson 08 uses these loops to search over possible answers, so it assumes you know them.

The idea in three words

Every template keeps a range: the part of the list that could still hold the answer. It has a left end, called lo, and a right end, called hi. The range starts as the whole list.

On each step the loop picks a middle index, called mid, and checks one value there. Then it moves one end so the range gets smaller. The loop stops when the range has no positions left to check, or when one position is the answer.

Two things must be true for the loop to work. The range must shrink on every step. And the answer, if it exists, must always stay inside the range. The templates below are built so that both are true.

Write mid as lo + (hi - lo) / 2 and not as (lo + hi) / 2. The two give the same answer for small numbers. For large numbers the first form is safe, because lo + hi can be larger than the biggest int. The largest int on most systems is 2,147,483,647. If lo and hi are both above 1,100,000,000, their sum goes past that limit and wraps to a wrong value.

Shape 1: find an exact value

This is the search you already know. You have a sorted list and a target value, and you want the index of the target, or a signal that it is missing. The range is closed on both ends. That means lo and hi are both positions that could still hold the target. The loop runs while lo is at or before hi.

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

The lines lo = mid + 1 and hi = mid - 1 are the two moves. When the value at mid is too small, the target must be to the right of mid, and mid itself is already ruled out. So lo jumps past it. The same logic moves hi to the left.

The loop ends in one of two ways. Either it returns the index, or lo passes hi. When lo passes hi, the range is empty, so the target is not in the list.

The cast static_cast<int>(a.size()) is there because a.size() returns an unsigned type, and mixing it with a signed int produces a warning. The mistakes section below shows that warning.

Worked example: finding 23

Use this sorted list, with positions counted from zero.

index:  0   1   2    3    4    5    6    7    8    9
value:  2   5   8   12   16   23   38   56   72   91

Look for 23. The range starts as 0 to 9.

Three checks found the value. A list of 10 values needs at most four checks here, because each check throws away about half of what is left.

Now look for 7, which is not in the list. The range again starts as 0 to 9. The first check is at 4, value 16, so lo becomes 5. The next check is at 7, value 56, so hi becomes 6. The next check is at 5, value 23, so hi becomes 4. Now lo is 5 and hi is 4. The loop stops and returns -1.

Running it

The program below checks both searches. Save it as find.cpp and build it with g++ -std=c++20 -Wall -o find find.cpp.

#include <iostream>
#include <vector>
using namespace std;
 
int find_exact(const vector<int>& a, int target) {
    int lo = 0;
    int hi = static_cast<int>(a.size()) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}
 
int main() {
    vector<int> a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    cout << "find 23 -> " << find_exact(a, 23) << "\n";
    cout << "find 7  -> " << find_exact(a, 7) << "\n";
    return 0;
}

The output is:

find 23 -> 5
find 7  -> -1

Shape 2: first true

Many questions are not "where is this value". They are "where does the answer change". You have a yes-or-no question about each position, and the answers follow one pattern: no, no, no, then yes, yes, yes. You want the first position that says yes.

Call the question a predicate. A predicate is a function that takes a position and returns true or false. For this shape the predicate must change only once, from false to true, as the position moves right. A sorted list gives you that for free. For example, "is the value at this position at least 20" is false for small values and true for large ones.

Take the same list as before and ask for the first position whose value is at least 20. The answer is position 5, which holds 23.

index:  0   1   2    3    4    5    6    7    8    9
value:  2   5   8   12   16   23   38   56   72   91
at 20?  no  no  no  no  no  yes  yes  yes  yes  yes

The template for this shape is below. The predicate is passed in as a function, so the same loop works for any yes-or-no question about positions. template <typename Pred> lets the function accept any predicate type, including a lambda (a small unnamed function written inline).

template <typename Pred>
int first_true(int n, Pred pred) {
    int lo = 0;
    int hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (pred(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

This template uses a half-open range. The range from lo up to hi includes lo and does not include hi. At the start, hi equals n, which is one past the last valid position. That value is a real answer. If no position says yes, the loop returns n, and the caller can check for that case.

The two moves have clear meanings. When pred(mid) is true, mid might be the first yes, so the answer is at mid or to its left. The move hi = mid keeps mid in the range. When pred(mid) is false, mid is not the answer, and neither is anything to its left. The move lo = mid + 1 throws it away.

The loop stops when lo equals hi. The range then has one position, and that position is the first yes, or n if there is none.

Worked example: first value at least 20

With n equal to 10, the range starts as 0 to 10. The table shows each step.

Now lo and hi are both 5, so the loop stops and returns 5.

Try a question with no yes at all: the first value at least 100. Every check says no, so lo keeps moving right until it reaches hi, which is 10. The function returns 10. That is why the caller must treat n as "not found".

Running it

#include <iostream>
#include <vector>
using namespace std;
 
template <typename Pred>
int first_true(int n, Pred pred) {
    int lo = 0;
    int hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (pred(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
 
int main() {
    vector<int> a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = static_cast<int>(a.size());
    auto at_least_20 = [&](int i) { return a[i] >= 20; };
    auto at_least_100 = [&](int i) { return a[i] >= 100; };
    cout << "first index with a[i] >= 20: " << first_true(n, at_least_20) << "\n";
    cout << "first index with a[i] >= 100: " << first_true(n, at_least_100) << "\n";
    return 0;
}

The output is:

first index with a[i] >= 20: 5
first index with a[i] >= 100: 10

The standard library has this search as std::lower_bound. It returns an iterator instead of an index. Learning the template still matters, because the same loop works for questions that are not about plain values.

Shape 3: last true

The mirror question asks for the last yes in a list that starts with yes and then switches to no. The predicate is true, true, true, then false, false. You want the last position that still says yes.

Take the same list and ask for the last position whose value is at most 16. The answer is position 4, which holds 16.

index:    0    1    2    3    4    5    6
value:    2    5    8   12   16   23   38
<= 16?   yes  yes  yes  yes  yes   no   no

The template uses a closed range. Both lo and hi are positions that could still be the answer. The first check makes sure position 0 is a yes. If it is not, there is no yes anywhere, and the function returns -1.

template <typename Pred>
int last_true(int n, Pred pred) {
    if (n == 0 || !pred(0)) return -1;
    int lo = 0;
    int hi = n - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        if (pred(mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

The important difference is the middle. Here mid is rounded up: (hi - lo + 1) / 2 instead of (hi - lo) / 2. The reason is explained in the next section, because the wrong rounding causes the infinite loop.

Worked example: last value at most 16

The range starts as 0 to 6, because the list has seven values. Position 0 is a yes, so the loop runs.

Now lo and hi are both 4, so the loop stops and returns 4.

The first step's middle is 0 + (6 - 0 + 1) / 2, which is 3. With floor rounding, (6 - 0) / 2 is also 3, so this example does not show the difference. The next section does.

How the infinite loop happens

A loop is infinite when some update leaves the range exactly as it was. The most common cause is pairing lo = mid with a floor middle.

Look at this broken version of shape 3. It is the same as the correct one, except the middle is rounded down and the loop has a step counter so it stops after a few steps.

#include <iostream>
using namespace std;
 
int last_true_broken(int n, int (*pred)(int), int max_steps, int& steps) {
    int lo = 0;
    int hi = n - 1;
    steps = 0;
    while (lo < hi) {
        if (++steps > max_steps) return -2;
        int mid = lo + (hi - lo) / 2;
        if (pred(mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}
 
int always_yes(int) { return 1; }
 
int main() {
    int steps = 0;
    int r = last_true_broken(2, always_yes, 6, steps);
    cout << "broken version on n=2, always true: result " << r << " after " << steps << " steps\n";
    return 0;
}

Run it on a list of two values where both are yes. The predicate always returns 1.

broken version on n=2, always true: result -2 after 7 steps

The loop never ended. The result -2 is the step counter's stop signal, not an answer. Here is why. The range is 0 to 1. The middle is 0 + (1 - 0) / 2, which is 0. The predicate says yes, so lo = mid sets lo to 0. lo was already 0. The range is still 0 to 1, and the next step does exactly the same thing.

The rule that prevents this is simple. When an update sets an end to mid, the middle must be strictly past the end it replaces whenever the loop runs. Rounding up gives that. When lo < hi, the middle lo + (hi - lo + 1) / 2 is at least lo + 1. So lo = mid always moves lo right.

The other update, hi = mid - 1 in shape 3 and hi = mid in shape 2, is safe with the matching rounding. Shape 2 uses floor rounding with hi = mid. When lo < hi, the floor middle is at most hi - 1, so hi = mid always moves hi left. Shape 3 uses round-up rounding with lo = mid, and that also moves its end. Each template pairs its rounding with its update, and that pairing is what matters.

The pairing rule

When you write your own binary search, check the update that moves an end onto mid. If it is lo = mid, round up. If it is hi = mid, round down. Moves that step past mid are safe with either rounding.

Shape 1 has the same risk

Shape 1 never sets an end to mid. Both of its updates step past mid. So shape 1 cannot loop forever in the way shape 3 can. It can still loop forever if you write lo = mid by mistake. For a list of two values where the target is larger than the first value, the mistake keeps lo at 0 and the loop never ends. Keep the + 1 and - 1 in every update you write.

Checking a template against the standard library

A template that looks right can still be wrong on an edge case. The safest way to check it is to compare it with a simple, slow method on many random inputs. For this lesson the simple method is the standard library: std::lower_bound finds the first position that is not less than a value, and std::upper_bound finds the first position that is greater than a value.

The checker below builds random sorted lists with repeated values, runs each template, and compares the result with the standard library. Repeated values matter, because they are where off-by-one errors show up.

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
 
int check_count = 0;
 
void expect_equal(int got, int want, const char* label) {
    ++check_count;
    if (got != want) {
        cout << "FAIL " << label << ": got " << got << ", want " << want << "\n";
        exit(1);
    }
}
 
// The three templates from this lesson go here.
 
int main() {
    srand(7);
    for (int round = 0; round < 2000; ++round) {
        int n = rand() % 12;
        vector<int> v(n);
        int x = 0;
        for (int& e : v) { x += rand() % 4; e = x; }
        int target = rand() % (x + 3);
 
        int want_idx = -1;
        for (int i = 0; i < n; ++i) if (v[i] == target) { want_idx = i; break; }
        int got_idx = find_exact(v, target);
        if (want_idx == -1) expect_equal(got_idx, -1, "find_exact missing");
        else expect_equal(v[got_idx], target, "find_exact value");
 
        auto ge = [&](int i) { return v[i] >= target; };
        int lb = static_cast<int>(lower_bound(v.begin(), v.end(), target) - v.begin());
        expect_equal(first_true(n, ge), lb, "first_true");
 
        auto le = [&](int i) { return v[i] <= target; };
        int ub = static_cast<int>(upper_bound(v.begin(), v.end(), target) - v.begin());
        expect_equal(last_true(n, le), ub - 1, "last_true");
    }
    cout << "random checks passed: " << check_count << "\n";
    return 0;
}

The expect_equal helper stops the program at the first mismatch and prints both values. That makes a failure easy to read. The find_exact, first_true and last_true functions must be defined above main, as in the earlier listings.

The output is:

random checks passed: 6000

The count is 6000 because each of the 2000 rounds makes three checks. A passing run does not prove a template is correct for every input. It does catch most off-by-one errors quickly, and it is cheap enough to keep in a test file.

Common mistakes

Mixing the two range styles

Shape 1 uses a closed range, where hi is a valid position and the loop condition is lo <= hi. Shapes 2 and 3 use a half-open or a rounded range, and their conditions are lo < hi. Copying hi = mid - 1 into shape 2 skips the answer. The result can come back one position too small. Pick one template for each question, and do not mix their updates.

Returning the wrong value when nothing matches

Shape 2 returns n when no position is true, not -1. A caller that checks if (i == -1) will never catch that case, and then reads past the end of the list. Write the check as if (i == n), or use the template's own convention and document it next to the function.

Comparing a signed index with an unsigned size

a.size() returns an unsigned type, which cannot hold a negative number. int i is signed, so it can. Comparing them makes the compiler warn you. Here is a real warning from g++ 15 with -Wall, for this loop:

#include <vector>
int main() {
    std::vector<int> a = {1, 2, 3};
    for (int i = 0; i < a.size(); ++i) {}
    return 0;
}

loop.cpp:4:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    4 |     for (int i = 0; i < a.size(); ++i) {}
      |                     ~~^~~~~~~~~~

The warning is harmless here, because i is never negative. It can hide a real bug. On an empty list, a.size() - 1 wraps to a huge unsigned number, not -1. Cast the size to int once, as the templates do, and keep all the indexes in int.

Using the wrong predicate direction

Shape 2 needs false followed by true. Shape 3 needs true followed by false. If you pass a predicate that changes the other way, the loop still runs and still returns a position, but the position is not the answer. Before you call a template, write the pattern for your list with yes and no, and check that it matches the shape.

Practice

Exercise 1: trace a miss

Trace find_exact on the list 3, 6, 9, 14, 21, looking for 10. Write each lo, hi, mid and the result.

Show the answer

Start with lo 0 and hi 4. The middle is 2, the value is 9, and 9 is less than 10, so lo becomes 3. The range is now 3 to 4. The middle is 3, the value is 14, and 14 is more than 10, so hi becomes 2. Now lo is 3 and hi is 2, so the loop stops. The function returns -1, because 10 is not in the list.

Exercise 2: first value at least 6

Use first_true to find the first index in 1, 3, 3, 5, 7, 7, 9 where the value is at least 6. What index does it return?

Show the answer

It returns 4. The values at indexes 0 to 3 are 1, 3, 3 and 5, which are all below 6. Index 4 holds 7, which is the first value at least 6.

Exercise 3: last value at most 3

Use last_true on the list 1, 3, 3, 5, 7 with the question "is the value at most 3". What index does it return?

Show the answer

It returns 2. Indexes 0, 1 and 2 hold 1, 3 and 3, which are at most 3. Index 3 holds 5, which is not. The last yes is index 2.

Exercise 4: find the bug

This loop is meant to find the first index whose value is at least x, in a sorted array a with n values. It loops forever on the array 1, 2 with x equal to 5, where n is 2. Find the bug and fix it.

int lo = 0;
int hi = n;
while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (a[mid] < x) lo = mid;
    else hi = mid;
}
return lo;

Show the answer

The bug is lo = mid. When a[mid] is less than x, the value at mid is not the answer, so mid should be thrown away with lo = mid + 1. With lo 0 and hi 2, the middle is 1 and a[1] is 2, which is less than 5. So lo becomes 1. Now lo is 1 and hi is 2, and the middle is 1 + (2 - 1) / 2, which is 1 again. The same update sets lo to 1 again, and the range never shrinks. The fix is if (a[mid] < x) lo = mid + 1;, and the rest stays the same. The corrected loop is the first-true template with the predicate a[i] >= x, and for this array it returns 2, which is n, meaning no value is at least 5.

Exercise 5: worst case for 1000 values

A sorted array holds 1000 values. For any target, what is the most times find_exact can run its loop body? Explain why in one or two sentences.

Show the answer

The most is 10. Each check removes the middle and leaves at most half of the range for the next check. A range of 1000 values becomes at most 500, then 250, 125, 62, 31, 15, 7, 3, 1 and finally 0. That is 10 checks. A program that counts the checks for every target from -1 to 2000 on a list of the 1000 even numbers 0 to 1998 prints worst iterations for n=1000: 10.

Summary

• Binary search keeps a range with two ends, lo and hi, and cuts it in half on each step.
• Use the closed-range loop lo <= hi to find an exact value, and move the ends with mid + 1 and mid - 1.
• Use the half-open loop lo < hi with hi = mid for the first position where a yes-or-no question turns true.
• Use the round-up middle with lo = mid for the last position where the question is still true.
• Round the middle so that an update which sets an end to mid always moves that end, or the loop never stops.
• Test any template against a simple slow method on random inputs, with repeated values included.