# Debugging `lower_bound`

## Analysis of Failures

The original implementation has **three critical bugs**:

### Bug 1: Incorrect `lo` update in the "less than" branch
```python
if a[mid] < target:
    lo = mid  # WRONG: should be lo = mid + 1
```
When `a[mid] < target`, the answer must be **strictly greater than** `mid`, so `lo` should jump to `mid + 1`. Setting `lo = mid` can cause an infinite loop (e.g., when `lo=2, hi=3`, `mid=2`, `a[2] < target` → `lo` stays `2`, loop never terminates).

### Bug 2: Incorrect `hi` update in the "greater/equal" branch
```python
else:
    hi = mid - 1  # WRONG: should be hi = mid
```
When `a[mid] >= target`, `mid` is a **candidate** for the answer (it might be the first such index). Excluding it by setting `hi = mid - 1` can skip the correct answer. The search space should shrink to `[lo, mid]`, not `[lo, mid-1]`.

### Bug 3: Wrong initial `hi`
```python
hi = len(a) - 1  # WRONG: should be len(a)
```
The answer can be `len(a)` (no element ≥ target). With `hi = len(a)-1`, the search space never includes the "past-the-end" case. We need `hi = len(a)` so that `lo` can reach `len(a)`.

### Bug 4: Return value logic
Even if the loop terminates, returning `lo` without verifying it's within bounds or handling the empty-array case correctly can yield wrong results. With the fixes above, returning `lo` is correct because the invariant guarantees `lo` is the first index where `a[lo] >= target` (or `len(a)` if none exists).

---

## 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 upper bound
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1      # answer must be > mid
        else:
            hi = mid          # mid is a candidate; keep it in range
    return lo
```

---

## Loop Invariant

**Invariant**: At every iteration of the `while` loop, the following holds:

> `a[0..lo-1]` are all **strictly less than** `target`, and `a[hi..len(a)-1]` are all **greater than or equal to** `target` (or `hi == len(a)` meaning no such elements exist yet), and the answer lies in `[lo, hi]`.

More precisely:

- **`a[lo] >= target`** is *not* guaranteed during the loop; rather:
  - All indices `< lo` have values `< target`.
  - All indices `>= hi` have values `>= target` (or `hi == len(a)`).
  - The true answer is in `[lo, hi]`.

At termination (`lo == hi`), `lo` is the smallest index such that `a[lo] >= target`, or `len(a)` if none exists.

---

## Runnable Tests

```python
def test_lower_bound():
    # --- Empty array ---
    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], 6) == 1, "Single element less than target"
    assert lower_bound([5], 4) == 0, "Single element greater than target"

    # --- All elements less than target ---
    assert lower_bound([1, 2, 3], 4) == 3, "All elements < target"

    # --- All elements greater than or equal to target ---
    assert lower_bound([1, 2, 3], 1) == 0, "First element >= target"
    assert lower_bound([1, 2, 3], 0) == 0, "Target below all elements"

    # --- Target not present, between elements ---
    assert lower_bound([1, 3, 5, 7], 4) == 2, "Target between elements"
    assert lower_bound([1, 3, 5, 7], 6) == 3, "Target between elements"
    assert lower_bound([1, 3, 5, 7], 8) == 4, "Target beyond all elements"

    # --- Duplicates ---
    assert lower_bound([1, 2, 2, 2, 3], 2) == 1, "First occurrence of duplicate"
    assert lower_bound([1, 2, 2, 2, 3], 3) == 4, "Target equals last duplicate block"
    assert lower_bound([2, 2, 2, 2], 2) == 0, "All duplicates equal target"
    assert lower_bound([2, 2, 2, 2], 1) == 0, "Target below all duplicates"
    assert lower_bound([2, 2, 2, 2], 3) == 4, "Target above all duplicates"

    # --- Boundary targets ---
    assert lower_bound([1, 2, 3], 1) == 0, "Target equals first element"
    assert lower_bound([1, 2, 3], 3) == 2, "Target equals last element"
    assert lower_bound([1, 2, 3], 2) == 1, "Target equals middle element"

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

    # --- Two-element edge case (infinite loop trigger in buggy version) ---
    assert lower_bound([1, 2], 2) == 1, "Two elements, target equals second"
    assert lower_bound([1, 2], 1) == 0, "Two elements, target equals first"
    assert lower_bound([1, 2], 3) == 2, "Two elements, target beyond both"

    print("All tests passed!")

test_lower_bound()
```

**Output:**
```
All tests passed!
```

---

## Summary of Fixes

| Bug | Original | Fixed |
|---|---|---|
| `lo` update | `lo = mid` | `lo = mid + 1` |
| `hi` update | `hi = mid - 1` | `hi = mid` |
| Initial `hi` | `len(a) - 1` | `len(a)` |
| Infinite loop risk | Yes (when `lo=mid`) | No (`lo` always advances) |
| Missed answer | Yes (when `a[mid] == target`) | No (`mid` stays in range) |

The corrected version correctly implements **binary search for the lower bound** with a clean loop invariant and handles all edge cases including empty arrays, duplicates, and boundary targets.