Binary Search — The Complete Guide

function binarySearch(nums: number[], target: number): number {
  let lo = 0, hi = nums.length - 1;

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }

  return -1; // not found
}
// Loop: lo <= hi (inclusive on both ends)
// Update: lo = mid + 1 or hi = mid - 1 (never mid itself)
// Terminates when: lo > hi (search space empty)
// Use for: "find target", "does target exist?"

function firstTrue(lo: number, hi: number, condition: (mid: number) => boolean): number {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (condition(mid)) {
      hi = mid;       // mid satisfies — might be the answer, keep it
    } else {
      lo = mid + 1;   // mid doesn't satisfy — discard it
    }
  }

  return lo; // lo === hi === first position where condition is true
}

// Loop: lo < hi (converge to a single point)
// When condition is true: hi = mid (keep mid as candidate)
// When condition is false: lo = mid + 1 (discard mid)
// Terminates when: lo === hi
// Use for: "first occurrence", "lower bound", "minimum X such that..."
// CRITICAL: condition must be monotonic: false...false, true...true

function lastTrue(lo: number, hi: number, condition: (mid: number) => boolean): number {
  while (lo < hi) {
    const mid = lo + Math.ceil((hi - lo) / 2); // ceiling!
    if (condition(mid)) {
      lo = mid;       // mid satisfies — might be the answer, keep it
    } else {
      hi = mid - 1;   // mid doesn't satisfy — discard it
    }
  }

  return lo; // lo === hi === last position where condition is true
}

// Key difference: mid uses Math.ceil to avoid infinite loop when lo + 1 === hi
// When condition is true: lo = mid (keep mid as candidate)
// When condition is false: hi = mid - 1 (discard mid)
// Use for: "last occurrence", "upper bound", "maximum X such that..."

function search(nums: number[], target: number): number {
  let lo = 0, hi = nums.length - 1;

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;

    // Left half is sorted
    if (nums[lo] <= nums[mid]) {
      if (nums[lo] <= target && target < nums[mid]) {
        hi = mid - 1; // target is in the sorted left half
      } else {
        lo = mid + 1; // target is in the right half
      }
    }
    // Right half is sorted
    else {
      if (nums[mid] < target && target <= nums[hi]) {
        lo = mid + 1; // target is in the sorted right half
      } else {
        hi = mid - 1; // target is in the left half
      }
    }
  }

  return -1;
}
// Key insight: at least one half is always sorted.
// Check if target is in the sorted half. If yes, search there. If no, search the other half.

// "Find the minimum X such that condition(X) is true"
function searchOnAnswer(lo: number, hi: number): number {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (canAchieve(mid)) {
      hi = mid;     // mid works — try smaller
    } else {
      lo = mid + 1; // mid doesn't work — need larger
    }
  }
  return lo;
}

// Examples of canAchieve:
// - Koko: can she eat all bananas at speed mid in h hours?
// - Ship packages: can we ship all in d days with capacity mid?
// - Split array: can we split into m subarrays with max sum ≤ mid?
// All are O(n) checks, giving O(n log(range)) total.

Array: [1, 3, 5, 7, 9, 11, 13, 15]
Index:  0  1  2  3  4  5   6   7
Target: 7

Step 1: lo=0, hi=7, mid=3
  nums[3] = 7 === target ✓
  Return 3

Done in 1 step! (Best case — target is at the midpoint)

---

Now let's find target = 11:

Step 1: lo=0, hi=7, mid=3
  nums[3] = 7 < 11 → lo = 4

Step 2: lo=4, hi=7, mid=5
  nums[5] = 11 === target ✓
  Return 5

Done in 2 steps!

---

Now let's find target = 6 (not in array):

Step 1: lo=0, hi=7, mid=3
  nums[3] = 7 > 6 → hi = 2

Step 2: lo=0, hi=2, mid=1
  nums[1] = 3 < 6 → lo = 2

Step 3: lo=2, hi=2, mid=2
  nums[2] = 5 < 6 → lo = 3

Step 4: lo=3 > hi=2 → loop ends
  Return -1 (not found)

4 steps for 8 elements. log₂(8) = 3. Worst case is ⌊log₂(n)⌋ + 1.

Array: [4, 5, 6, 7, 0, 1, 2]
Index:  0  1  2  3  4  5  6
Target: 0

Step 1: lo=0, hi=6, mid=3
  nums[3] = 7 ≠ 0
  Is left half sorted? nums[0]=4 <= nums[3]=7 → YES
  Is target in [4, 7)? 0 < 4 → NO
  → lo = 4 (search right half)

Step 2: lo=4, hi=6, mid=5
  nums[5] = 1 ≠ 0
  Is left half sorted? nums[4]=0 <= nums[5]=1 → YES
  Is target in [0, 1)? 0 >= 0 and 0 < 1 → YES
  → hi = 4 (search left half)

Step 3: lo=4, hi=4, mid=4
  nums[4] = 0 === target ✓
  Return 4

Key insight at each step:
- Determine which half is sorted (compare nums[lo] with nums[mid])
- Check if target falls in the sorted range
- If yes, search there. If no, search the other half.
- This works because at least one half is ALWAYS properly sorted.

Is there a MONOTONIC property you can exploit?
├── NO  → Not Binary Search. Consider linear scan, hashing, or DP.
└── YES → What are you searching for?
          ├── Exact value in sorted array → Template 1 (lo <= hi)
          ├── First position where condition is true → Template 2 (lo < hi, hi = mid)
          ├── Last position where condition is true → Template 3 (lo < hi, lo = mid, ceil)
          └── Minimum/maximum answer satisfying condition → Search on Answer (Template 2)

Checklist before coding:
1. What is the search space? [lo, hi]
2. What is the predicate? condition(mid) → boolean
3. Is the predicate monotonic? false...false, true...true?
4. Which template? (exact / first true / last true)
5. What do I return? (lo / hi / mid / -1)