# 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 fundamentally, the search space `[0, len(a))` must include the possibility that no element satisfies the condition, which requires `hi` to start at `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` can cause an **infinite loop** when `hi = lo + 1` and `a[mid] < target` (since `mid == lo`, `lo` never advances).

### Bug 3: Incorrect `hi` update in the `>=` 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 space by setting `hi = mid`. Setting `hi = mid - 1` excludes a valid candidate and can miss the correct answer.

### Bug 4: Loop condition interacts badly with wrong updates
With `lo = mid` (instead of `mid + 1`), when `hi = lo + 1`, `mid = lo`, and if `a[mid] < target`, `lo` stays at `mid`, causing an **infinite loop**.

### Bug 5: Return value
Even if the loop terminated correctly, returning `lo` without ensuring it's within `[0, len(a)]` could return an out-of-bounds index in edge cases.

---

## 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)  # search space is [lo, hi)
    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:

> **Invariant**: `a[0..lo-1] < target` and `a[hi..len(a)-1] >= target` (with the convention that empty ranges satisfy their condition vacuously).

Equivalently:
- All indices `< lo` have values **strictly less than** `target`.
- All indices `>= hi` have values **greater than or equal to** `target`.
- The answer lies in `[lo, hi]`.

**Initialization**: `lo = 0`, `hi = len(a)`. The range `[0, len(a))` covers all indices. No elements are known to satisfy either condition yet, so the invariant holds vacuously.

**Maintenance**:
- If `a[mid] < target`: `mid` is too small, so we set `lo = mid + 1`. Now `a[0..mid] < target` holds, preserving the invariant.
- If `a[mid] >= target`: `mid` could be the answer, so we set `hi = mid`. Now `a[mid..len(a)-1] >= target` holds, preserving the invariant.

**Termination**: When `lo == hi`, the search space is empty. By the invariant, `a[0..lo-1] < target` and `a[lo..len(a)-1] >= target`. Thus `lo` is the first index with `a[lo] >= target`, or `len(a)` if none exists.

---

## Runnable Tests

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

    # --- 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"

    # --- Duplicates ---
    assert lower_bound([1, 2, 2, 2, 3], 2) == 1, "First occurrence of duplicate"
    assert lower_bound([1, 2, 2, 2, 3], 1) == 0, "Target equals first element"
    assert lower_bound([1, 2, 2, 2, 3], 3) == 4, "Target equals last element"
    assert lower_bound([1, 2, 2, 2, 3], 4) == 5, "Target greater than all"
    assert lower_bound([1, 2, 2, 2, 3], 0) == 0, "Target less than all"

    # --- Boundary targets ---
    assert lower_bound([1, 3, 5, 7], 1) == 0, "Target equals minimum"
    assert lower_bound([1, 3, 5, 7], 7) == 3, "Target equals maximum"
    assert lower_bound([1, 3, 5, 7], 0) == 0, "Target below minimum"
    assert lower_bound([1, 3, 5, 7], 8) == 4, "Target above maximum"
    assert lower_bound([1, 3, 5, 7], 4) == 2, "Target between elements"

    # --- All same values ---
    assert lower_bound([2, 2, 2, 2], 2) == 0, "All equal to target"
    assert lower_bound([2, 2, 2, 2], 1) == 0, "Target below all"
    assert lower_bound([2, 2, 2, 2], 3) == 4, "Target above all"

    # --- Negative numbers ---
    assert lower_bound([-5, -3, -1, 0, 2], -3) == 1, "Negative target found"
    assert lower_bound([-5, -3, -1, 0, 2], -6) == 0, "Target below all negatives"
    assert lower_bound([-5, -3, -1, 0, 2], 3) == 5, "Target above all"

    # --- Large array with many duplicates ---
    arr = [1] * 1000
    assert lower_bound(arr, 1) == 0, "Large array, target present"
    assert lower_bound(arr, 0) == 0, "Large array, target below"
    assert lower_bound(arr, 2) == 1000, "Large array, target above"

    print("All tests passed!")

test_lower_bound()
```

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

## Summary of Fixes

| Bug | Original | Fixed |
|-----|----------|-------|
| `hi` init | `len(a) - 1` | `len(a)` |
| `lo` update | `lo = mid` | `lo = mid + 1` |
| `hi` update | `hi = mid - 1` | `hi = mid` |
| Infinite loop risk | `lo = mid` can stall | `lo = mid + 1` always progresses |
| Missed candidates | `hi = mid - 1` skips valid answers | `hi = mid` keeps candidates |

The corrected version uses the standard **half-open interval** `[lo, hi)` binary search pattern, which cleanly handles all edge cases including empty arrays, duplicates, and out-of-range targets.