Find the First Faulty Build: From Testing Every Build to Halving

Testing builds in order costs one test per build; because every build after the first faulty one is also faulty, each test can rule out half of the rest.

Halving the range of builds finds the first faulty one in O(log n) tests, where testing them in order costs one test per build. A team has 16 builds of an app, numbered in the order they were made. Build 1 worked and build 16 is known to be faulty: something broke along the way and stayed broken. Each test means installing a build and running it, so tests are slow, and the task is to find the first faulty build with as few of them as possible.

The brute force tests build 1, then build 2, and so on, stopping at the first faulty one. That costs one test per build up to the answer, O(n) tests for n builds, and here, where the answer is build 11, it takes 11. The repeated work is that each fine result says more than the loop uses: once a build is fine, every build before it is fine too, and once a build is faulty, every build after it is faulty. The predicate "this build is faulty" is monotone, false up to the first faulty build and true from there on, so one test can rule out half of the builds that remain.

Testing in order against halving

In orderO(n) tests

Test build 1, then 2, then 3, and stop at the first faulty one. Each test rules out one build.

HalvingO(log n) tests

Test the middle build of the range. Faulty means the first faulty build is this one or earlier; fine means it is later. Each test rules out half the range.

Halving the builds 1 to 16 when build 11 is the first faulty one

Inputbuilds 1 to 16; build 16 is known to be faulty

Start
1. 1low
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16high
The first faulty build is somewhere from 1 to 16
Test 1: build 8 fine
1. 1low
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8mid
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16high
Build 8 is fine, so builds 1 to 8 are all fine: low moves to 9
Test 2: build 12 faulty
1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9low
10. 10
11. 11
12. 12mid
13. 13
14. 14
15. 15
16. 16high
Build 12 is faulty, so the first faulty build is 12 or earlier: high moves to 12
Test 3: build 10 fine
1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9low
10. 10mid
11. 11
12. 12high
13. 13
14. 14
15. 15
16. 16
Build 10 is fine, so builds 9 and 10 are too: low moves to 11
Test 4: build 11 faulty
1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11lowmid
12. 12high
13. 13
14. 14
15. 15
16. 16
Build 11 is faulty: high moves to 11
Done
1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11lowhigh
12. 12
13. 13
14. 14
15. 15
16. 16
low meets high at build 11 after four tests

ResultBuild 11 is the first faulty build, found in 4 tests.

The listing runs both versions on the same 16 builds and counts the tests each one made.

builds.pypy

first_faulty = 11
newest = 16


def is_faulty(build: int) -> bool:
    return build >= first_faulty


def linear() -> tuple[int, int]:
    tests = 0
    for build in range(1, newest + 1):
        tests += 1
        if is_faulty(build):
            return build, tests
    return newest, tests


def halving() -> tuple[int, int]:
    low, high, tests = 1, newest, 0
    while low < high:
        mid = low + (high - low) // 2
        tests += 1
        if is_faulty(mid):
            high = mid
        else:
            low = mid + 1
    return low, tests


print("testing in order: build %d after %d tests" % linear())
print("halving:          build %d after %d tests" % halving())

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

testing in order: build 11 after 11 tests
halving:          build 11 after 4 tests

Both find build 11, the first in 11 tests and the second in 4. For 1,000 builds the halving search needs at most 10 tests, against up to 1,000 in order, because 2¹⁰ = 1,024. The search starts with high at 16 rather than one past it, since build 16 is already known to be faulty and the answer is certain to lie in the range. The same reasoning drives tools that hunt for the change that broke a program, such as git bisect.

Binary Search

← → move through sections and cards