Test iOS binary search boundaries on a cloud Mac

After implementing your list logic on Windows, you may move the Swift code to a cloud Mac for validation. The detail most likely to slip through is not whether a value can be found, but where duplicate values should be inserted. Chat timelines, segmented scales, and indexes of ordered records can all depend on binary search. An off-by-one position may pass ordinary test cases yet drop records on edge-case inputs. Here, a standalone script establishes an executable contract without launching a simulator or relying on network data.

Define the two insertion boundaries first

Assume the input is an array of integers sorted in ascending order. The lower bound returns the first position whose value is greater than or equal to the target. The upper bound returns the first position whose value is strictly greater than the target. Subtracting the lower bound from the upper bound gives the number of occurrences.

For example, searching for 2 in [1, 2, 2, 4] produces a lower bound of 1 and an upper bound of 3. Searching for 5 returns 4 for both: this is an insertion position at the end, not a failed search.

A returned position may equal the array’s length, but an index used to read an element may not. Check the range before accessing the element. Do not substitute the last element’s index for the insertion position at the end.

These functions do not use a -1 sentinel or sort the input automatically. Automatic sorting would conceal unsorted input from the caller and could disrupt the existing order among records.

Implement the search with a half-open interval

After signing in to the cloud Mac, create BoundsCheck.swift in your working directory. First run xcrun --find swift to confirm that the toolchain is available, then add the implementation below. The search interval is always [lo, hi), with the initial upper endpoint set to the array’s length.

func lowerBound(_ values: [Int], _ target: Int) -> Int {
    var lo = 0
    var hi = values.count
    while lo < hi {
        let mid = lo + (hi - lo) / 2
        if values[mid] < target {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

func upperBound(_ values: [Int], _ target: Int) -> Int {
    var lo = 0
    var hi = values.count
    while lo < hi {
        let mid = lo + (hi - lo) / 2
        if values[mid] <= target {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

The only difference between the two functions is the comparison condition, but that difference determines which side includes duplicate values. The midpoint uses lo + (hi - lo) / 2 to avoid adding the endpoints directly. Every iteration must shrink the interval. Do not update the left endpoint to mid, or the loop may fail to terminate for a two-element input.

An empty array needs no special branch: the loop is skipped and the function returns zero. Do not introduce count - 1 to handle empty arrays; that would bring back negative indices and closed-interval termination conditions.

Check every small case against a linear reference

The reference implementation should be simple, not another binary search. Append the following code to the same file. It enumerates every nondecreasing array of length zero through six with values from zero through three, then checks targets both inside and outside that range.

func verify(_ values: [Int]) {
    for target in -1...4 {
        let lower = lowerBound(values, target)
        let upper = upperBound(values, target)
        let expectedLower =
            values.firstIndex(where: { $0 >= target }) ?? values.count
        let expectedUpper =
            values.firstIndex(where: { $0 > target }) ?? values.count

        precondition(lower == expectedLower)
        precondition(upper == expectedUpper)
        precondition(lower <= upper)
        precondition(values[..<lower].allSatisfy { $0 < target })
        precondition(values[lower...].allSatisfy { $0 >= target })
        precondition(values[..<upper].allSatisfy { $0 <= target })
        precondition(values[upper...].allSatisfy { $0 > target })
    }
}

func enumerate(_ prefix: [Int], remaining: Int, minimum: Int) {
    if remaining == 0 {
        verify(prefix)
        return
    }
    for value in minimum...3 {
        enumerate(prefix + [value],
                  remaining: remaining - 1,
                  minimum: value)
    }
}

for length in 0...6 {
    enumerate([], remaining: length, minimum: 0)
}
verify([Int.min, 0, Int.max])
precondition(lowerBound([Int.min, 0, Int.max], Int.min) == 0)
precondition(upperBound([Int.min, 0, Int.max], Int.max) == 3)

Run xcrun swift BoundsCheck.swift. An exit code of zero means all assertions passed; a failure ends the process with a nonzero status. The script avoids ordinary assert checks, which may be removed in optimized builds. Do not use compiler options that disable safety checks, either.

Apply the contract to your application interface

To check whether an element exists, first obtain its lower bound. It is a match only if the position is less than the array’s length and the value at that position equals the target. To retrieve all duplicates, use the lower..<upper slice. If the target is absent, the slice is naturally empty.

Keep sorting and comparison consistent

If the array contains records sorted by timestamp, the search must use the same timestamp semantics. Sorting by ascending time but comparing display strings during the search will fail even when the algorithm itself is correct.

When records with the same timestamp must retain their arrival order, insertion at the upper bound is an option. If business priorities also matter, define a complete sort key first rather than expecting an insertion position to stand in for ordering rules. The comparison conditions shown here cannot be reused unchanged for a descending array.

The array must also remain unchanged during the search. If you obtain a position asynchronously and then modify the array, that position may already be stale. Perform the search and insertion within the same isolation domain, or operate on the same immutable snapshot.

Turn failing inputs into a regression checklist

When integrating this into project tests, retain three layers of checks: fixed application-specific cases, exhaustive enumeration of small arrays, and the ordering contract for real records. Do not merely check that the returned position is within the valid range; a valid position can still be off by one.

• Cover empty arrays, single-element arrays, arrays with all equal values, and targets beyond either end.
• Check that every value to the left of the lower bound is less than the target and every value from the upper bound onward is greater than the target.
• Check that the duplicate range’s length matches the count from a linear scan.
• Save each failing array, target, and expected position as a fixed test case.
• Rerun the checks with the toolchain and build configuration actually used.

Exhaustive testing of small cases does not prove correctness for all integer inputs, but it systematically covers duplicate handling and the paths by which the interval shrinks. Even if the implementation later switches to a generic comparator, retain the linear reference and partition assertions so that optimizations continue to honor the same interface contract.

Frequently asked questions