Binary Search In Swift Without Off-By-One Errors

Binary search is one of those algorithms that looks tiny after it works and somehow feels slippery every time you write it from memory. Should high start at count or count - 1? Should the loop be < or <=? When do we move mid, and when do we move past it?

The way I like to make it less scary is to stop writing “a binary search” and write one specific binary search with one specific invariant.

In this post we will use a half-open range:

low..<high

That means low is included, and high is excluded. The search space starts as 0..<array.count. An empty array is naturally 0..<0, so the loop never runs. There is no special count - 1 setup, and that removes a surprising number of mistakes.

We are going to build four helpers:

• lowerBound(of:): first index whose value is greater than or equal to the target
• upperBound(of:): first index whose value is greater than the target
• binarySearch(for:): an exact search built on lowerBound
• insertionIndex(for:): where a new value should be inserted to keep the array sorted

All of these assume the array is already sorted in ascending order.

Lower bound

Let’s start with the most useful version:

extension Array where Element: Comparable {
    func lowerBound(of target: Element) -> Int {
        var low = 0
        var high = count

        while low < high {
            let mid = low + (high - low) / 2

            if self[mid] < target {
                low = mid + 1
            } else {
                high = mid
            }
        }

        return low
    }
}

The return value is the first index where the element is not less than target. In other words, it is the first place the target could appear.

let numbers = [1, 3, 3, 3, 7, 9]

numbers.lowerBound(of: 0) // 0
numbers.lowerBound(of: 3) // 1
numbers.lowerBound(of: 4) // 4
numbers.lowerBound(of: 10) // 6

The last result, 6, is not a valid subscript for this array. That is okay. It means “the insertion position is after the last element.” Returning count is an important part of the design, not an error case.

The key invariant is:

• Every index before low is known to contain a value less than target.
• Every index at or after high is no longer part of the remaining search.
• The answer is somewhere in low...high, and the active search range is low..<high.

When self[mid] < target, mid cannot be the lower bound. Neither can anything before it, because the array is sorted. So we move low to mid + 1.

When self[mid] >= target, mid might be the answer. We do not skip past it. Moving high to mid preserves it as the possible boundary the loop can return.

That second branch is where a lot of off-by-one bugs happen. If a value might be the answer, keep it.

The midpoint

You will often see binary search written like this:

let mid = (low + high) / 2

For small arrays, that is fine. The safer habit is:

let mid = low + (high - low) / 2

This avoids adding two large integers together before dividing. Swift traps on integer overflow in normal debug builds, and optimized builds are still not a great place to invite overflow-adjacent logic. The safer midpoint style costs nothing and works everywhere we need it.

Upper bound

upperBound is almost the same function, but the comparison changes. It returns the first index whose value is greater than the target.

extension Array where Element: Comparable {
    func upperBound(of target: Element) -> Int {
        var low = 0
        var high = count

        while low < high {
            let mid = low + (high - low) / 2

            if self[mid] <= target {
                low = mid + 1
            } else {
                high = mid
            }
        }

        return low
    }
}

With the same array:

let numbers = [1, 3, 3, 3, 7, 9]

numbers.upperBound(of: 0) // 0
numbers.upperBound(of: 3) // 4
numbers.upperBound(of: 4) // 4
numbers.upperBound(of: 10) // 6

The difference between lower bound and upper bound is duplicate handling.

For 3, lower bound returns 1, the first 3. Upper bound returns 4, the index immediately after the last 3.

That gives us a clean range of matching values:

let lower = numbers.lowerBound(of: 3)
let upper = numbers.upperBound(of: 3)
let matches = lower..<upper

Array(numbers[matches]) // [3, 3, 3]

If lower == upper, there are no matching values. That also works for targets outside the array.

Exact search

Now exact search becomes small. We ask lower bound where the target could be, then check whether the value is actually there.

extension Array where Element: Comparable {
    func binarySearch(for target: Element) -> Int? {
        let index = lowerBound(of: target)

        guard index < count, self[index] == target else {
            return nil
        }

        return index
    }
}

This version returns the first matching index when duplicates exist.

let numbers = [1, 3, 3, 3, 7, 9]

numbers.binarySearch(for: 3) // Optional(1)
numbers.binarySearch(for: 5) // nil
numbers.binarySearch(for: 9) // Optional(5)

There are binary searches that return any matching index as soon as they see it. That is useful too, but the duplicate behavior is less precise. Building exact search on lowerBound gives us a stable answer: if the value exists, we get its first position.

Insertion index

The insertion index is just the lower bound:

extension Array where Element: Comparable {
    func insertionIndex(for newElement: Element) -> Int {
        lowerBound(of: newElement)
    }
}

That places the new element before existing equal elements. If you want to insert after existing equal elements, use upperBound instead.

var numbers = [1, 3, 3, 7]

let beforeDuplicates = numbers.lowerBound(of: 3) // 1
let afterDuplicates = numbers.upperBound(of: 3)  // 3

numbers.insert(3, at: beforeDuplicates)
// [1, 3, 3, 3, 7]

Both insertion points keep the array sorted. The difference only matters when equal values carry some extra meaning outside the value itself, like records sorted by score or date.

Tests that catch the usual mistakes

Binary search bugs tend to hide in the boring cases: empty arrays, one-element arrays, values before the first element, values after the last element, and duplicates.

Here is a lightweight table-driven test setup using assert, so it can run in a Swift file or playground without importing anything:

struct SearchCase {
    let values: [Int]
    let target: Int
    let lower: Int
    let upper: Int
    let exact: Int?
}

let cases = [
    SearchCase(values: [], target: 4, lower: 0, upper: 0, exact: nil),
    SearchCase(values: [4], target: 3, lower: 0, upper: 0, exact: nil),
    SearchCase(values: [4], target: 4, lower: 0, upper: 1, exact: 0),
    SearchCase(values: [4], target: 5, lower: 1, upper: 1, exact: nil),
    SearchCase(values: [1, 3, 5, 7], target: 0, lower: 0, upper: 0, exact: nil),
    SearchCase(values: [1, 3, 5, 7], target: 5, lower: 2, upper: 3, exact: 2),
    SearchCase(values: [1, 3, 5, 7], target: 8, lower: 4, upper: 4, exact: nil),
    SearchCase(values: [1, 3, 3, 3, 7], target: 3, lower: 1, upper: 4, exact: 1),
    SearchCase(values: [1, 3, 3, 3, 7], target: 4, lower: 4, upper: 4, exact: nil)
]

for testCase in cases {
    assert(
        testCase.values.lowerBound(of: testCase.target) == testCase.lower,
        "Wrong lower bound for \(testCase)"
    )

    assert(
        testCase.values.upperBound(of: testCase.target) == testCase.upper,
        "Wrong upper bound for \(testCase)"
    )

    assert(
        testCase.values.binarySearch(for: testCase.target) == testCase.exact,
        "Wrong exact search for \(testCase)"
    )
}

I like this style of test for small algorithms because each row tells a story. You can scan the input, target, and expected values together. If you accidentally write while low <= high, start high at count - 1, or move high to mid - 1 in lower bound, one of these cases should complain pretty quickly.

We can add a separate insertion table too:

struct InsertionCase {
    let values: [Int]
    let newValue: Int
    let expectedIndex: Int
}

let insertionCases = [
    InsertionCase(values: [], newValue: 10, expectedIndex: 0),
    InsertionCase(values: [10], newValue: 5, expectedIndex: 0),
    InsertionCase(values: [10], newValue: 10, expectedIndex: 0),
    InsertionCase(values: [10], newValue: 20, expectedIndex: 1),
    InsertionCase(values: [1, 3, 3, 7], newValue: 3, expectedIndex: 1),
    InsertionCase(values: [1, 3, 3, 7], newValue: 6, expectedIndex: 3)
]

for testCase in insertionCases {
    assert(
        testCase.values.insertionIndex(for: testCase.newValue) == testCase.expectedIndex,
        "Wrong insertion index for \(testCase)"
    )
}

The duplicate insertion case is intentional. It proves that insertionIndex(for:) uses lower-bound behavior, so equal values are inserted before the existing group.

Complexity

Each function halves the remaining search range on every loop, so the time complexity is O(log n).

The space complexity is O(1) because we only keep a few integer variables. If you call insert(_:at:) after finding an insertion index, the search is still O(log n), but the array insertion itself is O(n) because later elements may need to shift.

The whole trick is deciding what low and high mean before you write the loop. With the half-open low..<high invariant, high can safely start at count, empty arrays behave naturally, and lowerBound becomes the small reusable building block for exact search, duplicates, and insertion indexes.