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

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

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

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

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

Solution to All Linked List solutions Github

Easy Problems

1. Binary Search to find X in sorted array

   • Find an element X in a sorted array using binary search
   • Time Complexity: O(log n)
   • Space Complexity: O(1)

2. Implement Lower Bound

   • 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

   • 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

   • 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

   • 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

   • 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

   • 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

   • Find X in a rotated sorted array
   • Time Complexity: O(log n)
   • Space Complexity: O(1)

9. Search in Rotated Sorted Array II

   • 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

    • 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

    • 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

    • 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

    • Find the peak index in a mountain array
    • Time Complexity: O(log n)
    • Space Complexity: O(1)

14. Find Peak Element

    • Find any peak element in an array
    • Time Complexity: O(log n)
    • Space Complexity: O(1)

15. Square Root of a Number

    • 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

   • 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

   • 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

   • 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

   • 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

   • 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

   • Find the kth missing positive number in a sorted array
   • Time Complexity: O(log n)
   • Space Complexity: O(1)

7. 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

   • 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

   • 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

    • 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

    • 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

    • 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

    • 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

    • 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

    • 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

    • 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

    • Find a peak element in a 2D matrix
    • Time Complexity: O(n * log(m))
    • Space Complexity: O(1)

18. Matrix Median

    • Find the median of a row-wise sorted matrix
    • Time Complexity: O(32 * r * log(c))
    • Space Complexity: O(1)