Binary search boundary: find the first true position

Prove the discarded region

A linear scan for the first value at least target is an O(n)-time, O(1)-space baseline. In a sorted array, the predicate nums[i] >= target changes at most once from false to true. Binary search finds that transition without inspecting every position. The useful invariant divides the array into three regions:

Initialize lo=0, hi=n; both proven regions are empty. Choose a midpoint in the unresolved interval. If its value is smaller, sortedness proves every position through mid is also smaller, so set lo=mid+1. Otherwise mid itself could be the first true position, so set hi=mid, preserving it as the boundary. This distinction is the proof of the updates, not a formula to memorize.

The nonnegative interval length strictly decreases each iteration. At termination, all positions before lo are smaller and all from lo onward are at least target, so lo is the required boundary, including n if the true region is empty. The search loop takes O(log(n+1)) comparisons and O(1) auxiliary space. The supplied public function first validates types and sortedness in O(n), so its end-to-end worst-case time is O(n). This cost is intentional: it honors the invalid-input contract rather than claiming to validate ordering logarithmically.

Follow-up 1: count exact target occurrences

Predict the changed predicate for the other edge: find the first value strictly greater than target. Subtract the lower boundary from that upper boundary.

Do not search for equality and then scan duplicates: that loses the logarithmic search bound when almost every value equals target.

Follow-up 2: thousands of queries on one immutable snapshot

Move validation to snapshot construction and expose a trusted internal search; copying to a tuple also has O(n) time and space cost. Total work becomes O(n + q log(n+1)) for q queries, with O(n) snapshot storage. A senior candidate states each discarded-region proof and tests all-equal arrays. A lead candidate defines snapshot ownership so mutation cannot invalidate sortedness between validation and search; a checked list reference alone cannot guarantee that.

Run and check

From the repository root:

cd curriculum/01-code/02-data-structures-algorithms/problems/11-binary-search-boundary
python -m unittest -v test_solution.py

Reference implementation (download file, source below) · Contract and oracle tests (download file, source below). Read the tests after your attempt. A green reference suite verifies the supplied implementation; it does not demonstrate independent transfer. Reimplement one follow-up with the reference closed and explain which old invariant no longer holds.

def _integers(values):
    if not isinstance(values, (list, tuple)) or any(type(x) is not int for x in values):
        raise ValueError("expected a list or tuple of integers, excluding bool")

def lower_bound(nums, target):
    _integers(nums)
    if type(target) is not int or any(nums[i] > nums[i + 1] for i in range(len(nums) - 1)):
        raise ValueError("expected sorted integers and integer target")
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

import itertools
import unittest
from solution import lower_bound

class BoundaryTests(unittest.TestCase):
    def test_contract(self):
        self.assertEqual(lower_bound([1, 3, 3, 8], 3), 1)
        self.assertEqual(lower_bound([1, 3, 3, 8], 4), 3)
        self.assertEqual(lower_bound([1, 3, 3, 8], 9), 4)
        self.assertEqual(lower_bound([], 2), 0)
        for nums, target in [([3, 1], 2), ([True], 1), (None, 2), ([1], 1.0)]:
            with self.assertRaises(ValueError):
                lower_bound(nums, target)

    def test_linear_boundary_oracle(self):
        for n in range(8):
            for nums in itertools.combinations_with_replacement(range(-2, 3), n):
                for target in range(-3, 4):
                    result = lower_bound(nums, target)
                    expected = next((i for i, value in enumerate(nums) if value >= target), n)
                    self.assertEqual(result, expected)
                    self.assertTrue(all(value < target for value in nums[:result]))
                    self.assertTrue(all(value >= target for value in nums[result:]))

if __name__ == "__main__":
    unittest.main()