> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Binary Search

> Master binary search on arrays and on the answer—the technique that separates good from great

# Binary Search

<img src="https://mintcdn.com/devweeekends/AEOaWh79Ur7CdHHv/images/courses/cp/binary-search-visualization.svg?fit=max&auto=format&n=AEOaWh79Ur7CdHHv&q=85&s=563c30c2c9ca0156bf8e1025a431989f" alt="Binary Search Visualization" width="1080" height="1080" data-path="images/courses/cp/binary-search-visualization.svg" />

## The Mental Model

Binary search is like playing "guess the number" optimally. Instead of guessing randomly, you always guess the middle. With each guess, you eliminate half the possibilities. This is why binary search is O(log n)—even with a billion elements, you need at most 30 guesses.

<Note>
  **Pattern Recognition Signals**:

  * "Minimum/Maximum value that satisfies condition"
  * "Find first/last occurrence"
  * Sorted array or **monotonic property**
  * Constraints allow O(log n) or O(n log n)
</Note>

***

## The Two Types of Binary Search

### Type 1: Binary Search on Index

Find an element or position in a sorted array.

### Type 2: Binary Search on Answer

The answer is a number in a range. Check if each candidate answer is valid. The validity forms a monotonic sequence (all NO, then all YES, or vice versa).

<Tip>
  **The Insight**: Binary search works whenever you have a **monotonic predicate**—a condition that's false for all values up to some point, then true for all values after (or vice versa).
</Tip>

***

## Template: Binary Search on Index

### Finding Exact Element

```cpp theme={null}
int binarySearch(vector<int>& arr, int target) {
    int lo = 0, hi = arr.size() - 1;
    
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // Avoid overflow
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    
    return -1;  // Not found
}
```

### Finding Lower Bound (First >= Target)

```cpp theme={null}
int lowerBound(vector<int>& arr, int target) {
    int lo = 0, hi = arr.size();
    
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        
        if (arr[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid;  // Don't exclude mid, it might be the answer
        }
    }
    
    return lo;  // First position where arr[i] >= target
}
```

### Finding Upper Bound (First > Target)

```cpp theme={null}
int upperBound(vector<int>& arr, int target) {
    int lo = 0, hi = arr.size();
    
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        
        if (arr[mid] <= target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    
    return lo;  // First position where arr[i] > target
}
```

***

## Template: Binary Search on Answer

This is the **game-changer** pattern. Many problems that seem impossible become easy with this technique.

```cpp theme={null}
// General template
bool canAchieve(int x) {
    // Return true if 'x' is achievable/valid
    // This function must be monotonic!
}

int binarySearchOnAnswer() {
    int lo = MIN_POSSIBLE_ANSWER;
    int hi = MAX_POSSIBLE_ANSWER;
    int answer = -1;
    
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        
        if (canAchieve(mid)) {
            answer = mid;       // mid is valid
            hi = mid - 1;       // Try to find smaller valid (for minimum)
            // lo = mid + 1;    // Try to find larger valid (for maximum)
        } else {
            lo = mid + 1;       // Need larger value
            // hi = mid - 1;    // Need smaller value (for maximum)
        }
    }
    
    return answer;
}
```

***

## Classic Pattern: Minimum Maximum

**Problem Type**: "Minimize the maximum" or "Maximize the minimum"

**Example**: Split array into K subarrays to minimize the maximum subarray sum.

**Approach**: Binary search on the answer (the maximum sum). For each candidate, check if we can split into ≤ K subarrays.

```cpp theme={null}
bool canSplit(vector<int>& arr, int maxSum, int k) {
    int count = 1;
    int currentSum = 0;
    
    for (int x : arr) {
        if (x > maxSum) return false;  // Single element too large
        
        if (currentSum + x > maxSum) {
            count++;
            currentSum = x;
        } else {
            currentSum += x;
        }
    }
    
    return count <= k;
}

int splitArray(vector<int>& nums, int k) {
    int lo = *max_element(nums.begin(), nums.end());
    int hi = accumulate(nums.begin(), nums.end(), 0);
    
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        
        if (canSplit(nums, mid, k)) {
            hi = mid;  // Try smaller maximum
        } else {
            lo = mid + 1;
        }
    }
    
    return lo;
}
```

**Codeforces Problems**:

| Problem                   | Rating | Link                                                         |
| ------------------------- | ------ | ------------------------------------------------------------ |
| Aggressive Cows (Classic) | 1500   | [SPOJ](https://www.spoj.com/problems/AGGRCOW/)               |
| Magic Powder              | 1500   | [CF 670D2](https://codeforces.com/problemset/problem/670/D2) |
| Ropes                     | 1200   | [CF 579B](https://codeforces.com/problemset/problem/579/B)   |

***

## Classic Pattern: Kth Element

**Problem**: Find the Kth smallest element in sorted matrix / merged sorted arrays.

**Approach**: Binary search on the value. Count how many elements are ≤ mid.

```cpp theme={null}
int kthSmallest(vector<vector<int>>& matrix, int k) {
    int n = matrix.size();
    int lo = matrix[0][0];
    int hi = matrix[n-1][n-1];
    
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        
        // Count elements <= mid
        int count = 0;
        int col = n - 1;
        for (int row = 0; row < n; row++) {
            while (col >= 0 && matrix[row][col] > mid) {
                col--;
            }
            count += col + 1;
        }
        
        if (count < k) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    
    return lo;
}
```

***

## Common Mistakes

<Warning>
  **Mistake 1: Wrong Loop Condition**

  ```cpp theme={null}
  // For exact search
  while (lo <= hi)  // Use <= 

  // For lower/upper bound
  while (lo < hi)   // Use <
  ```
</Warning>

<Warning>
  **Mistake 2: Integer Overflow in Mid Calculation**

  ```cpp theme={null}
  // WRONG: Can overflow if lo + hi > INT_MAX
  int mid = (lo + hi) / 2;

  // CORRECT
  int mid = lo + (hi - lo) / 2;
  ```
</Warning>

<Warning>
  **Mistake 3: Wrong Bounds Update**
  When searching for minimum valid:

  * If `canAchieve(mid)` is true → `hi = mid` (not `mid - 1`)
  * If false → `lo = mid + 1`

  When searching for maximum valid:

  * If `canAchieve(mid)` is true → `lo = mid + 1`
  * If false → `hi = mid - 1`
</Warning>

<Warning>
  **Mistake 4: Non-Monotonic Predicate**
  Binary search only works if the predicate is monotonic. Always verify:

  * If canAchieve(x) is true, is canAchieve(x+1) also true? (or vice versa)
</Warning>

***

## The Binary Search Decision Tree

```
Need to find something in sorted array?
├── Exact element → Standard binary search (lo <= hi)
├── First >= target → Lower bound
├── First > target → Upper bound
└── Last <= target → Upper bound - 1

Need to optimize (min/max) something?
├── Can you define canAchieve(x)?
│   ├── Is it monotonic? → Binary search on answer
│   └── Not monotonic → Different technique
└── No clear predicate → Not binary search
```

***

## Advanced: Ternary Search

For **unimodal functions** (one peak/valley), use ternary search:

```cpp theme={null}
// Find maximum of unimodal function f
double ternarySearch(double lo, double hi) {
    for (int i = 0; i < 100; i++) {  // Precision iterations
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        
        if (f(m1) < f(m2)) {
            lo = m1;
        } else {
            hi = m2;
        }
    }
    
    return (lo + hi) / 2;
}
```

***

## Practice Problems

### Beginner (800-1200)

| Problem           | Pattern                 | Link                                                       |
| ----------------- | ----------------------- | ---------------------------------------------------------- |
| Binary Search     | Basic                   | [CSES](https://cses.fi/problemset/task/1091)               |
| Interesting drink | Lower bound             | [CF 706B](https://codeforces.com/problemset/problem/706/B) |
| Hamburgers        | Binary search on answer | [CF 371C](https://codeforces.com/problemset/problem/371/C) |

### Intermediate (1200-1500)

| Problem              | Pattern                     | Link                                                       |
| -------------------- | --------------------------- | ---------------------------------------------------------- |
| Multiplication Table | BS on answer, counting      | [CF 448D](https://codeforces.com/problemset/problem/448/D) |
| Ropes                | BS on answer (real numbers) | [CF 579B](https://codeforces.com/problemset/problem/579/B) |
| Children's Numbers   | BS + greedy                 | [CF 577B](https://codeforces.com/problemset/problem/577/B) |

### Advanced (1500-1800)

| Problem              | Pattern              | Link                                                         |
| -------------------- | -------------------- | ------------------------------------------------------------ |
| Magic Powder         | BS on answer         | [CF 670D2](https://codeforces.com/problemset/problem/670/D2) |
| Minimize the Maximum | Minimax BS           | [CF 1760E](https://codeforces.com/problemset/problem/1760/E) |
| Social Network       | BS + data structures | [CF 1234D](https://codeforces.com/problemset/problem/1234/D) |

***

## Key Takeaways

<CardGroup cols={2}>
  <Card title="Monotonic Predicate" icon="chart-line">
    Binary search works when canAchieve(x) is monotonic (all false, then all true).
  </Card>

  <Card title="Search on Answer" icon="bullseye">
    When asked to minimize/maximize, binary search on the answer is often the key.
  </Card>

  <Card title="Bound Selection" icon="arrows-left-right">
    Carefully choose lo and hi. lo = minimum possible, hi = maximum possible.
  </Card>

  <Card title="Off-by-One" icon="calculator">
    Use `lo < hi` for bounds, `lo <= hi` for exact search. Be precise.
  </Card>
</CardGroup>

***

## Next Up

<Card title="Chapter 7: Sorting & Custom Comparators" icon="arrow-right" href="/courses/competitive-programming/07-sorting">
  Learn strategic sorting techniques and how custom comparators unlock powerful problem-solving approaches.
</Card>