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

# Binary Search Problems and Its Variants

## Theory

You can use binary search if all these conditions are satisfied

**1. Monotonic Property**

> There must be a monotonic relationship in the search space:

* If some property/condition is true for X, it is also true for all values > X (or all values \< X).
* In other words, the answer space is sorted with respect to the property you’re checking.

**2. Eliminate Half the Space**
Each comparison tells us:

* If we're still in the "before" region → search right
* If we've found the transition → search left
* This eliminates half the search space

**3. Convergence**

* We always move toward the single element
* The loop condition left \< right ensures convergence
* We find the exact position of the single element

## Patterns

> Binary Search Loop Patterns: `left <= right` vs `left < right`

**Overview**
The choice between `while left <= right:` and `while left < right:` in binary search depends on the specific problem and
what you're trying to find. Here are the common patterns:

### Pattern 1: `while left <= right:` (Inclusive Search)

**When to Use:**

* **Finding exact target** in a sorted array
* **Finding first/last occurrence** of a target
* **Finding floor/ceil** values
* **Problems where you need to check the final element**

**Characteristics:**

* Loop continues until `left > right` (no elements left to check)
* Both `left` and `right` are inclusive bounds
* You typically return `-1` or a sentinel value if target not found
* The final state is `left = right + 1`

**Example: Standard Binary Search**

```python theme={null}
def search(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:  # Inclusive search
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # Target not found
```

**Example: Finding Floor Value**

```python theme={null}
def find_floor(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    result = -1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] <= target:
            result = mid  # Potential floor
            left = mid + 1  # Try to find larger floor
        else:
            right = mid - 1

    return result
```

### Pattern 2: `while left < right:` (Exclusive Search)

**When to Use:**

* **Finding minimum/maximum** in a range
* **Binary search on answer space** (optimization problems)
* **Problems where you're guaranteed to find an answer**
* **When you want to converge to a single element**

**Characteristics:**

* Loop continues until `left == right` (converges to single element)
* The final state is `left == right == answer`
* You typically return `left` or `right` (they're equal)
* No need for sentinel values

**Example: Finding Minimum in Rotated Array**

```python theme={null}
def find_min(nums: List[int]) -> int:
    left, right = 0, len(nums) - 1

    while left < right:  # Converge to minimum
        mid = (left + right) // 2

        if nums[mid] > nums[right]:
            left = mid + 1  # Min is in right half
        else:
            right = mid     # Min is in left half (including mid)

    return nums[left]  # left == right == index of minimum
```

**Example: Binary Search on Answer Space**

```python theme={null}
def min_eating_speed(piles: List[int], h: int) -> int:
    left, right = 1, max(piles)

    while left < right:  # Find minimum valid speed
        mid = (left + right) // 2

        if can_eat_all(mid, piles, h):
            right = mid  # Try smaller speed
        else:
            left = mid + 1  # Need larger speed

    return left  # left == right == minimum valid speed
```

### Key Differences Summary

| Aspect             | `left <= right`          | `left < right`               |
| :----------------- | :----------------------- | :--------------------------- |
| **Loop Condition** | `while left <= right:`   | `while left < right:`        |
| **Final State**    | `left = right + 1`       | `left = right`               |
| **Return Value**   | Usually `-1` or sentinel | Usually `left` or `right`    |
| **Use Case**       | Finding exact targets    | Finding min/max/optimization |
| **Guarantee**      | May not find target      | Always converges to answer   |
| **Bounds**         | Inclusive                | Converging                   |

### Decision Framework

**Use `left <= right` when:**

1. You're searching for an **exact target** that may not exist
2. You need to find **first/last occurrence** of a value
3. You're looking for **floor/ceil** values
4. You need to **check all possible positions**

**Use `left < right` when:**

1. You're finding the **minimum/maximum** in a range
2. You're doing **binary search on answer space**
3. You're guaranteed to find an answer
4. You want to **converge to a single element**

### Common Mistakes

1. **Using `left < right` for exact target search**: May miss the target if it's at the boundary
2. **Using `left <= right` for optimization problems**: May cause infinite loops or incorrect convergence
3. **Incorrect return values**: Returning wrong variable in final state
4. **Wrong mid calculation**: Can cause overflow or incorrect convergence

### Tips for Implementation

1. **Always consider the final state** of your variables
2. **Think about what you're returning** and when the loop terminates
3. **Test edge cases** to ensure your loop condition is correct
4. **Use inclusive search** when you need to check every possible position
5. **Use exclusive search** when you're converging to a guaranteed answer

***

## Problems

<Info>
  Solution to All Linked List solutions [Github](https://github.com/akshanshgusain/data_structures_algorithms_python/tree/master/binary_search)
</Info>

## Easy Problems

1. [Binary Search to find X in sorted array](https://leetcode.com/problems/binary-search/description/)
   * Find an element X in a sorted array using binary search
   * Time Complexity: O(log n)
   * Space Complexity: O(1)

2. [Implement Lower Bound](https://www.geeksforgeeks.org/problems/floor-in-a-sorted-array-1587115620/1?track=DSASP-Searching\&amp%253BbatchId=154\&utm_source=youtube\&utm_medium=collab_striver_ytdescription\&utm_campaign=floor-in-a-sorted-array)
   * Find the index of the first element that is greater than or equal to X
   * Time Complexity: O(log n)
   * Space Complexity: O(1)

3. [Implement Upper Bound](https://www.geeksforgeeks.org/problems/ceil-the-floor2802/1?utm_source=youtube\&utm_medium=collab_striver_ytdescription\&utm_campaign=ceil-the-floor)
   * Find the index of the first element that is greater than X
   * Time Complexity: O(log n)
   * Space Complexity: O(1)

4. [Search Insert Position](https://leetcode.com/problems/search-insert-position/description/)
   * Find the index where X should be inserted to maintain sorted order
   * Time Complexity: O(log n)
   * Space Complexity: O(1)

5. [Floor/Ceil in Sorted Array](https://www.geeksforgeeks.org/problems/ceil-the-floor2802/1?utm_source=youtube\&utm_medium=collab_striver_ytdescription\&utm_campaign=ceil-the-floor)
   * Find floor and ceil of X in a sorted array
   * Time Complexity: O(log n)
   * Space Complexity: O(1)

6. [Find First and Last Position of Element in Sorted Array](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/)
   * Find the first and last occurrence of X in a sorted array
   * Time Complexity: O(log n)
   * Space Complexity: O(1)

7. [Count Occurrences in Sorted Array](https://www.geeksforgeeks.org/problems/number-of-occurrence2259/1?utm_source=youtube\&utm_medium=collab_striver_ytdescription\&utm_campaign=number-of-occurrence)
   * Count the number of occurrences of X in a sorted array
   * Time Complexity: O(log n)
   * Space Complexity: O(1)

## Binary Search on an Unstored Array

### 1. There’s a monotonic (ordered) property, not necessarily sorted values

You need a binary-searchable condition or monotonic predicate. That is:

If a predicate P(i) is False for some index i, then it is also False for all j \< i (or j > i) — and vice versa.

This allows you to "eliminate" half the array on each step.

🔹 Example: Peak Element Problem
Array is unsorted, but:

If `arr[mid] < arr[mid + 1]`, you can move right — because there’s a guaranteed peak in that direction.

You don’t need sorted values — just a guarantee of direction.

### 2. Finding Rotation Point in Rotated Sorted Array

Even though the array is not sorted end-to-end, you can binary search for the minimum element (i.e., the rotation point)
because:

* One half is always sorted.
* The other half contains the inflection.
  So you use the condition `arr[mid] > arr[right]` to decide which half to discard.

### 3. Search in Bitonic Array (increasing then decreasing)

You can use binary search to:

* First find the maximum element (peak),
* Then binary search separately in the increasing and decreasing parts.

This works because:

* Each half is sorted (one increasing, one decreasing).
* You have a structure to exploit.

### 4. First/Last Position That Satisfies a Condition

Even in unsorted input, if you're searching along a time axis, distance, or function input, you can binary search the input domain rather than the array directly.

🔹 Example: Minimize the maximum load (Scheduling problem)
Given N jobs and K workers, what's the minimum possible maximum load?

* The array is job durations (unsorted), but:
* The predicate “Can you assign with max load X?” is monotonic → if you can assign with load X, you can with X + 1.

So you binary search over the answer space, not the array itself.

8. [Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/description/)
   * Find X in a rotated sorted array
   * Time Complexity: O(log n)
   * Space Complexity: O(1)

9. [Search in Rotated Sorted Array II](https://leetcode.com/problems/search-in-rotated-sorted-array-ii/description/)
   * Find X in a rotated sorted array with duplicates
   * Time Complexity: O(log n) average, O(n) worst case
   * Space Complexity: O(1)

10. [Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/)
    * Find the minimum element in a rotated sorted array
    * Time Complexity: O(log n)
    * Space Complexity: O(1)

11. [Find out how many times the array has been rotated](https://www.geeksforgeeks.org/problems/rotation4723/1?utm_source=youtube\&utm_medium=collab_striver_ytdescription\&utm_campaign=rotation)
    * Find the number of times a sorted array has been rotated
    * Time Complexity: O(log n)
    * Space Complexity: O(1)

12. [Single Element in a Sorted Array](https://leetcode.com/problems/single-element-in-a-sorted-array/description/)
    * Find the single element in a sorted array where all elements appear twice except one
    * Time Complexity: O(log n)
    * Space Complexity: O(1)

13. [Peak Index in a Mountain Array](https://leetcode.com/problems/peak-index-in-a-mountain-array/description/)
    * Find the peak index in a mountain array
    * Time Complexity: O(log n)
    * Space Complexity: O(1)

14. [Find Peak Element](https://leetcode.com/problems/find-peak-element/description/)
    * Find any peak element in an array
    * Time Complexity: O(log n)
    * Space Complexity: O(1)

15. [Square Root of a Number](https://leetcode.com/problems/sqrtx/description/)
    * Find the square root of a number using binary search
    * Time Complexity: O(log n)
    * Space Complexity: O(1)

## Medium Problems

1. [Nth Root of a Number](https://www.geeksforgeeks.org/problems/nth-root-of-m5843/1?utm_source=youtube\&utm_medium=collab_striver_ytdescription\&utm_campaign=nth-root-of-m)
   * Find the nth root of a number using binary search
   * Time Complexity: O(n \* log(m \* 10^d)) where d is the number of decimal places
   * Space Complexity: O(1)

2. [Koko Eating Bananas](https://leetcode.com/problems/koko-eating-bananas/description/)
   * Find the minimum eating speed to eat all bananas within h hours
   * Time Complexity: O(n \* log(max(piles)))
   * Space Complexity: O(1)

3. [Minimum Days to Make M Bouquets](https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/)
   * Find the minimum days to make m bouquets
   * Time Complexity: O(n \* log(max(bloomDay)))
   * Space Complexity: O(1)

4. [Find the Smallest Divisor Given a Threshold](https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/description/)
   * Find the smallest divisor such that the sum of division results is less than or equal to threshold
   * Time Complexity: O(n \* log(max(nums)))
   * Space Complexity: O(1)

5. [Capacity to Ship Packages Within D Days](https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/description/)
   * Find the minimum capacity to ship all packages within d days
   * Time Complexity: O(n \* log(sum(weights) - max(weights)))
   * Space Complexity: O(1)

6. [Kth Missing Positive Number](https://leetcode.com/problems/kth-missing-positive-number/description/)
   * Find the kth missing positive number in a sorted array
   * Time Complexity: O(log n)
   * Space Complexity: O(1)

7. [Aggressive Cows](https://www.geeksforgeeks.org/problems/aggressive-cows/1?utm_source=youtube\&utm_medium=collab_striver_ytdescription\&utm_campaign=aggressive-cows)
   * Find the maximum minimum distance between cows
   * Time Complexity: O(n \* log(max(stalls) - min(stalls)))
   * Space Complexity: O(1)

8. [Book Allocation Problem](https://www.geeksforgeeks.org/problems/allocate-minimum-number-of-pages0937/1?utm_source=youtube\&utm_medium=collab_striver_ytdescription\&utm_campaign=allocate-minimum-number-of-pages)
   * Allocate books to students such that the maximum pages assigned to a student is minimum
   * Time Complexity: O(n \* log(sum(pages) - max(pages)))
   * Space Complexity: O(1)

9. [Split Array Largest Sum](https://leetcode.com/problems/split-array-largest-sum/description/)
   * Split array into k subarrays such that the largest sum is minimum
   * Time Complexity: O(n \* log(sum(nums) - max(nums)))
   * Space Complexity: O(1)

10. [Painter's Partition Problem](https://www.geeksforgeeks.org/problems/painters-partition-problem1532/1?utm_source=youtube\&utm_medium=collab_striver_ytdescription\&utm_campaign=painters-partition-problem)
    * Allocate boards to painters such that the time taken is minimum
    * Time Complexity: O(n \* log(sum(lengths) - max(lengths)))
    * Space Complexity: O(1)

11. [Minimize Max Distance to Gas Station](https://takeuforward.org/plus/dsa/problems/minimise-max-distance-to-gas-stations)
    * Find the minimum value of dist.
    * Time Complexity: O(n \* log(max\_distance / precision))
    * Space Complexity: O(1)

## Hard Problems

12. [Median of Two Sorted Arrays](https://leetcode.com/problems/median-of-two-sorted-arrays/description/)
    * Find the median of two sorted arrays
    * Time Complexity: O(log(min(n, m)))
    * Space Complexity: O(1)

13. [K-th Element of Two Sorted Arrays](https://www.geeksforgeeks.org/problems/k-th-element-of-two-sorted-array1317/1?utm_source=youtube\&utm_medium=collab_striver_ytdescription\&utm_campaign=k-th-element-of-two-sorted-array)
    * Find the k-th element of two sorted arrays
    * Time Complexity: O(log(min(n, m)))
    * Space Complexity: O(1)

## Matrix Problems

14. [Search in a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/description/)
    * Search for a target in a row-wise and column-wise sorted matrix
    * Time Complexity: O(log(m \* n))
    * Space Complexity: O(1)

15. [Search in a 2D Matrix II](https://leetcode.com/problems/search-a-2d-matrix-ii/description/)
    * Search for a target in a row-wise and column-wise sorted matrix
    * Time Complexity: O(m + n)
    * Space Complexity: O(1)

16. [Find Single Element in Sorted Array](https://leetcode.com/problems/single-element-in-a-sorted-array/description/)
    * Find the single element in a sorted array where all elements appear twice except one
    * Time Complexity: O(log n)
    * Space Complexity: O(1)

17. [Find Peak Element II](https://leetcode.com/problems/find-a-peak-element-ii/description/)
    * Find a peak element in a 2D matrix
    * Time Complexity: O(n \* log(m))
    * Space Complexity: O(1)

18. [Matrix Median](https://www.geeksforgeeks.org/problems/median-in-a-row-wise-sorted-matrix1527/1?utm_source=youtube\&utm_medium=collab_striver_ytdescription\&utm_campaign=median-in-a-row-wise-sorted-matrix)
    * Find the median of a row-wise sorted matrix
    * Time Complexity: O(32 \* r \* log(c))
    * Space Complexity: O(1)