# Binary Search — Part 1: The Pattern

Binary search halves the search space on every step, so it finds an answer among n candidates in **O(log n)**: 30 steps for a billion items. It applies far beyond "find x in a sorted array": any time candidates can be split into a **"no" part followed by a "yes" part** (a monotonic predicate), you can binary search for the boundary. That includes searching for a numeric *answer* such as a speed, a capacity or a time.

![Each step discards half of the remaining range](diagrams/01-binary-search.svg)

## 1. Three Flavours

| Flavour | Question | Example |
|---|---|---|
| **Exact match** | Is x present, and where? | Binary Search (704) |
| **Boundary (lower/upper bound)** | First index where `a[i] ≥ x` (or `> x`) | insert position, first/last occurrence, count of x |
| **Search on the answer** | Smallest value v such that `feasible(v)` is true | Koko Eating Bananas, ship packages, split array |

## 2. One Template to Rule Them All

Most bugs come from mixing up `<=` / `<` and `mid` / `mid ± 1`. Use **one** half-open template for everything and reason only about the predicate:

```typescript
function lowerBound(nums: number[], target: number): number {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (nums[mid] < target) lo = mid + 1; else hi = mid;
  }
  return lo;
}

function minFeasible(lo: number, hi: number, feasible: (x: number) => boolean): number {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (feasible(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}
```

```python
def lower_bound(nums, target):
    """First index i with nums[i] >= target (len(nums) if none)."""
    lo, hi = 0, len(nums)                 # search space [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1                    # answer is right of mid
        else:
            hi = mid                        # mid could be the answer
    return lo

def min_feasible(lo, hi, feasible):
    """Smallest x in [lo, hi] with feasible(x) True; feasible must be monotonic (F..F T..T)."""
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo
```

**Invariant:** the answer is always inside `[lo, hi)` (or `[lo, hi]` in `min_feasible`). Each iteration shrinks the range by at least one, so the loop terminates, and when `lo == hi` that's the answer.

- `upper_bound(x)` (first index with `a[i] > x`) is the same code with `<=` in the comparison.
- `count of x` = `upper_bound(x) − lower_bound(x)`.
- Python has these built in: `bisect.bisect_left` and `bisect.bisect_right`. C# has `Array.BinarySearch` (returns the bitwise complement of the insertion point when not found).

## 3. Search on the Answer

When asked for "the minimum X such that something is possible":

1. Identify the **range** of candidate answers `[lo, hi]` (e.g. speed 1 to max pile).
2. Write `feasible(x)`, usually a greedy O(n) check.
3. Confirm monotonicity: if x works, every larger x works too.
4. Binary search the boundary: total **O(n log range)**.

## 4. Rotated and Partially Sorted Arrays

In a rotated sorted array, **one half around `mid` is always sorted**. Check which half is sorted (`nums[lo] <= nums[mid]`), test whether the target lies inside that sorted half, and discard the other. The minimum of a rotated array is found by comparing `nums[mid]` with `nums[hi]`.

## Under the Hood: Overflow and Termination

`mid = (lo + hi) / 2` can overflow 32-bit integers in C#/Java when `lo + hi > 2³¹ − 1`; use `lo + (hi − lo) / 2`. In JavaScript, `(lo + hi) >>> 1` is a safe unsigned shift for array indices. Python integers don't overflow. Termination: with `lo < hi`, `mid` is always `< hi`, so `hi = mid` strictly shrinks the range and `lo = mid + 1` does too. If you write `lo = mid` instead, the loop can get stuck when `hi = lo + 1` (then you'd need `mid = (lo + hi + 1) / 2`).

## Common Pitfalls

1. **Mixing templates** (`<=` with `hi = mid`) → infinite loops or skipped answers.
2. **Non-monotonic predicate:** binary search silently returns garbage.
3. **Integer overflow** in `(lo + hi) / 2` in typed languages.
4. **Wrong answer range** in search-on-answer (e.g. lower bound 0 when the answer must be ≥ 1).
5. **Forgetting duplicates:** with repeated values, decide whether you want the first or last occurrence.

## Quick Reference

```text
lower_bound: lo,hi = 0,n; while lo<hi: mid; a[mid]<x → lo=mid+1 else hi=mid
upper_bound: same with a[mid] <= x
answer search: lo..hi range; feasible(mid) → hi=mid else lo=mid+1
rotated: one half is sorted; test target there
O(log n) · answer search O(n log range)
```