# Debugging `lower_bound`

## Analysis of Failures

The original function has **multiple critical bugs**:

### Bug 1: Incorrect `hi` initialization
```python
hi = len(a) - 1  # WRONG
```
`hi` should be `len(a)` (exclusive upper bound), not `len(a) - 1`. With `hi = len(a) - 1`, if all elements are `< target`, the loop may terminate with `lo == hi == len(a)-1`, returning an index that doesn't satisfy the condition. More critically, if `target` is greater than all elements, we need to return `len(a)`, but `hi` never reaches `len(a)`.

### Bug 2: Incorrect `lo` update in the `<` branch
```python
if a[mid] < target:
    lo = mid  # WRONG — should be lo = mid + 1
```
When `a[mid] < target`, `mid` cannot be the answer, so we must exclude it by setting `lo = mid + 1`. Setting `lo = mid` causes an **infinite loop** when `lo` and `hi` are adjacent (e.g., `lo=0, hi=1, mid=0` → `lo` stays `0` forever).

### Bug 3: Incorrect `hi` update in the `else` branch
```python
else:
    hi = mid - 1  # WRONG — should be hi = mid
```
When `a[mid] >= target`, `mid` **could** be the answer, so we must keep it in the search range by setting `hi = mid`. Setting `hi = mid - 1` excludes `mid`, potentially skipping the correct answer.

### Bug 4: Return value when no element satisfies the condition
Even if the loop terminated correctly, returning `lo` when `lo == hi == len(a)-1` would return an index whose value is `< target`, violating the contract.

---

## Corrected Implementation

```python
def lower_bound(a, target):
    """
    Return the first index i such that a[i] >= target,
    or len(a) if no such index exists.
    Assumes a is sorted in non-decreasing order.
    """
    lo, hi = 0, len(a)  # hi is exclusive
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1   # mid is too small; exclude it
        else:
            hi = mid       # mid could be the answer; keep it
    return lo
```

### Loop Invariant

At every iteration of the `while` loop:

> **All indices `< lo` have values `< target`, and all indices `>= hi` have values `>= target` (or `hi == len(a)` meaning no such index exists yet).**

More precisely:
- `a[0..lo-1] < target` (all elements before `lo` are strictly less than `target`)
- `a[hi..len(a)-1] >= target` (all elements from `hi` onward are at least `target`)

When the loop terminates (`lo == hi`), `lo` is the smallest index where `a[lo] >= target`, or `len(a)` if no such index exists.

---

## Runnable Tests

```python
def test_lower_bound():
    # --- Empty input ---
    assert lower_bound([], 5) == 0, "Empty array should return 0"

    # --- Target smaller than all elements ---
    assert lower_bound([1, 2, 3, 4, 5], 0) == 0, "Target below all → first index"

    # --- Target larger than all elements ---
    assert lower_bound([1, 2, 3, 4, 5], 6) == 5, "Target above all → len(a)"

    # --- Target equal to first element ---
    assert lower_bound([1, 2, 3, 4, 5], 1) == 0, "Target equals first element"

    # --- Target equal to last element ---
    assert lower_bound([1, 2, 3, 4, 5], 5) == 4, "Target equals last element"

    # --- Target not present, falls between elements ---
    assert lower_bound([1, 3, 5, 7], 4) == 2, "Target 4 → first >=4 is 5 at index 2"

    # --- Duplicates: first occurrence ---
    assert lower_bound([1, 2, 2, 2, 3], 2) == 1, "Duplicates → first occurrence of 2"

    # --- Duplicates: target not present but between duplicates ---
    assert lower_bound([1, 2, 2, 2, 3], 2.5) == 4, "Target 2.5 → first >=2.5 is 3 at index 4"

    # --- All elements equal ---
    assert lower_bound([3, 3, 3, 3], 3) == 0, "All equal to target → index 0"
    assert lower_bound([3, 3, 3, 3], 2) == 0, "Target below all → index 0"
    assert lower_bound([3, 3, 3, 3], 4) == 4, "Target above all → len(a)"

    # --- Single element ---
    assert lower_bound([5], 5) == 0, "Single element equal to target"
    assert lower_bound([5], 3) == 0, "Single element greater than target"
    assert lower_bound([5], 7) == 1, "Single element less than target → len(a)"

    # --- Negative numbers ---
    assert lower_bound([-5, -3, -1, 0, 2], -2) == 2, "Negative target → first >=-2 is -1 at index 2"

    # --- Large gap ---
    assert lower_bound([1, 100], 50) == 1, "Target between sparse elements"

    print("All tests passed!")

test_lower_bound()
```

### Expected Output
```
All tests passed!
```

## Summary of Fixes

| Bug | Original | Fixed | Reason |
|-----|----------|-------|--------|
| `hi` init | `len(a) - 1` | `len(a)` | Need exclusive upper bound to return `len(a)` when no element qualifies |
| `lo` update | `lo = mid` | `lo = mid + 1` | `mid` is excluded when `a[mid] < target`; prevents infinite loop |
| `hi` update | `hi = mid - 1` | `hi = mid` | `mid` is a candidate answer when `a[mid] >= target`; must keep it in range |
| Return | `return lo` (with broken logic) | `return lo` (with correct logic) | Now `lo` correctly points to first index with `a[lo] >= target` or `len(a)` |