Binary Search

// ── TEMPLATE 2: Lower bound ────────────────────────────────── // Use when: find first index where a[i] >= target. // Loop exits when lo == hi == insertion point. int lowerBound(vector& a, int target) { int lo = 0, hi = (int)a.size(); // hi = n (one past end) is valid while (lo < hi) { int mid = lo + (hi - lo) / 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; // first index with a[lo] >= target }

// ── TEMPLATE 3: Upper bound ────────────────────────────────── // Use when: find first index where a[i] > target. int upperBound(vector& a, int target) { int lo = 0, hi = (int)a.size(); while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] <= target) lo = mid + 1; // mid is not strictly greater else hi = mid; } return lo; // first index with a[lo] > target } // C++ equivalents: lower_bound(a.begin(),a.end(),t) and upper_bound(…)

</div>
<h3 class="section-subheading">1.2 — Template Comparison</h3>
<div class="ch-ed-problems">
  <table>
<thead>
<tr><th>Template</th><th>Loop Condition</th><th><code>hi</code> initialised to</th><th><code>lo/hi</code> Update</th><th>Returns</th></tr>
</thead>
<tbody>
<tr><td>Classic exact</td><td><code>lo &lt;= hi</code></td><td><code>n - 1</code></td><td><code>lo=mid+1</code> or <code>hi=mid-1</code></td><td>Index or <code>-1</code></td></tr>
<tr><td>Lower bound</td><td><code>lo &lt; hi</code></td><td><code>n</code></td><td><code>lo=mid+1</code> or <code>hi=mid</code></td><td>First idx &gt;= target</td></tr>
<tr><td>Upper bound</td><td><code>lo &lt; hi</code></td><td><code>n</code></td><td><code>lo=mid+1</code> or <code>hi=mid</code></td><td>First idx &gt; target</td></tr>
<tr><td>Answer space</td><td><code>lo &lt; hi</code> or <code>&lt;=</code></td><td>problem max</td><td>depends on feasibility</td><td>Optimal value</td></tr>
</tbody>
  </table>
</div>
</div>
<!-- Section 2 -->
<div class="chapter-section">
<h2 class="section-heading">Section 2 — Visual Diagrams: Binary Search in Action</h2>
<h3 class="section-subheading">Diagram 1 — Classic Binary Search</h3>
<div class="ch-code-wrap">
<span class="ch-code-label">Trace</span>
```text
Classic Binary Search: Target = 7
  Array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]   target = 7
  Index:  0  1  2  3  4   5   6   7   8   9

  Iteration 1: lo=0, hi=9, mid=4, a[mid]=9
    9 > 7  =>  search left half.  hi = mid-1 = 3.
  [1, 3, 5, 7] [9, 11, 13, 15, 17, 19]
   lo=0      hi=3

  Iteration 2: lo=0, hi=3, mid=1, a[mid]=3
    3 < 7  =>  search right half.  lo = mid+1 = 2.
  [1, 3] [5, 7]
          lo=2 hi=3

  Iteration 3: lo=2, hi=3, mid=2, a[mid]=5
    5 < 7  =>  lo = mid+1 = 3.
         [7]
          lo=3=hi=3

  Iteration 4: lo=3, hi=3, mid=3, a[mid]=7
    7 == 7  =>  FOUND at index 3.

  Total comparisons: 4 = ceil(log2(10)).  Without binary search: up to 10.

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

};

</div>
<h3 class="section-subheading">4. Follow-Up Questions</h3>
<ul>
  <li><strong>Q: What if the array has duplicates (LC 81)?</strong> When <code>a[lo] == a[mid]</code>, we cannot determine which half is sorted. Increment <code>lo</code> (<code>lo++</code>) to skip the duplicate and continue. Worst case degrades to O(n).</li>
  <li><strong>Q: Find the pivot index?</strong> Binary search for the minimum element (LC 153). The pivot is the index of the minimum.</li>
  <li><strong>Q: Why use <code>a[lo] &lt;= a[mid]</code> instead of <code>&lt;</code>?</strong> When <code>lo == mid</code> (two-element window), <code>a[lo] == a[mid]</code> and the left half of size 1 is trivially sorted. The <code>&lt;=</code> safely handles this.</li>
</ul>
</div>
<!-- Section 9 -->
<div class="chapter-section">
<h2 class="section-heading">Section 9 — Solved Problem 2: Koko Eating Bananas</h2>
<div class="insight-box">
<span class="insight-label">1. Observations & Core Idea</span>
<p>Koko has piles of bananas. She eats at speed k (k bananas per hour). Each hour she picks one pile and eats min(pile, k) bananas. Find the minimum k so she can eat all bananas in at most h hours.</p>
<ul>
<li>For a given speed <code>k</code>, hours needed = sum of <code>ceil(pile[i] / k)</code> over all piles.</li>
<li><strong>Monotone property:</strong> If speed <code>k</code> is feasible, then any speed <code>k' &gt; k</code> is also feasible. This enables binary search on <code>k</code>.</li>
<li>Search space: <code>lo = 1</code>, <code>hi = max(piles)</code>.</li>
<li>Binary search finds the minimum <code>k</code> where <code>feasible(k)</code> is true. This is the lower-bound template on the answer space.</li>
</ul>
</div>
<h3 class="section-subheading">2. Approach Comparison</h3>
<div class="ch-ed-problems">
  <table>
<thead>
<tr><th>Approach</th><th>Time</th><th>Space</th><th>Method</th></tr>
</thead>
<tbody>
<tr><td>Brute Force (Linear Scan)</td><td>O(n * M)</td><td>O(1)</td><td>Try every speed from 1 to M (max pile).</td></tr>
<tr><td>Binary Search on Answer</td><td>O(n log M)</td><td>O(1)</td><td>Binary search <code>lo</code> to <code>hi</code> boundary.</td></tr>
</tbody>
  </table>
</div>
<h3 class="section-subheading">3. Optimised Solution</h3>
<div class="ch-code-wrap">
<span class="ch-code-label">C++</span>
```cpp
class Solution {
    // Can Koko finish all piles at speed k within h hours?
    bool feasible(vector<int>& piles, long long k, int h) {
        long long hours = 0;
        for (int p : piles)
            hours += (p + k - 1) / k; // ceil(p / k)
        return hours <= h;
    }
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int lo = 1;
        int hi = *max_element(piles.begin(), piles.end());
        // Binary search: find minimum k where feasible(k) is true
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (feasible(piles, mid, h))
                hi = mid;      // mid works, try smaller
            else
                lo = mid + 1;  // mid too slow, need faster
        }
        return lo; // lo == hi == minimum feasible speed
    }
};