Binary Search

Use Cases

Use Case	Description	Example
Finding the First Occurrence of an Element	Given a sorted array with duplicate elements, find the index of the first occurrence of a value.	In the array [1, 2, 2, 2, 3], the first index of 2 is 1.
Finding the First Element Greater Than or Equal to a Target	Find the smallest element in a sorted array that is greater than or equal to a given value.	In the array [1, 3, 5, 7], for target 4, the lower bound returns index 2 (element 5).
Finding Insertion Points	Use the lower bound to determine the correct index for inserting a new element while maintaining sorted order.	In the array [1, 3, 5, 7], to insert 4, the lower bound returns 2, indicating 4 should be placed before 5.

Code Template

Initializing search range

The element we are looking for is in the range [left, right). (right is not included.)
Use < instead of <= to prevent infinite loop when the template range closed on the left, open on the right.

Update search range

Calculates the mid index of a search interval to avoid overflow and ensure accurate indexing.
Update the left or right boundary based on the output of valid().
left: the index of first valid() element.

Implenent valid function

Implenent valid function based on problem requirements.

def lower_bound(nums, target):
    left, right = 0, len(nums)
    while left < right:

Common mistakes

Wrong Boundary Condition

# Wrong
while left <= right:  # In the code template can lead to infinite loop
# Correct 
while left < right:

Wrong Initial Right Boundary

# Wrong: might miss last element
right = len(nums) - 1
# Correct: for lower_bound
right = len(nums)

Wrong Update of Left/Right Pointers

# Wrong: missing +1 when updating left
if not valid(nums[mid], target):
    left = mid  # This can lead to infinite loop
# Wrong: adding +1 when updating right
if valid(nums[mid], target):
    right = mid + 1  # This skips potential answer
# Correct:
if valid(nums[mid], target):
    right = mid
else:
    left = mid + 1

Issues and consideration

Custom Comparators: If using custom data types, ensure that the comparator correctly defines the ordering. This is crucial for the accuracy of the binary search.
Validation: The function will return 0 if the target is valid for all elements in the array (target is small than all other elements). The function will return len(nums) if the target is not valid for all elements in the array.

69. Sqrt(x)

class Solution:
    def mySqrt(self, x):
        left = 1
        right = x + 1
        while left < right:
            mid = left + (right - left) // 2
            if self.valid(mid, x):
                right = mid
            else:
                left = mid + 1
        # left - 1 is the index of first non valid() element
        return left - 1

    def valid(self, mid, x):
        return mid * mid > x

278. First Bad Version

class Solution:
    def firstBadVersion(self, n):
        left = 0
        right = n + 1
        while left < right:
            mid = left + (right - left) // 2
            if self.valid(mid):
                right = mid
            else:
                left = mid + 1
        return left

    def valid(self, mid):
        return isBadVersion(mid)

744. Find Smallest Letter Greater Than Target

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        left, right = 0, len(letters)
        while left < right:
            mid = left + (right - left) // 2
            if letters[mid] > target:
                right = mid
            else:
                left = mid + 1
        return letters[left % len(letters)]

875. Koko Eating Bananas

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        left, right = 1, max(piles)
        while left < right:
            mid = left + (right - left) // 2
            if self.valid(mid, piles, h):
                right = mid
            else:
                left = mid + 1
        return left

    def valid(self, k, piles, h):
        hours_needed = 0
        for pile in piles:
            hours_needed += (pile + k - 1) // k
        return hours_needed <= h

1011. Capacity To Ship Packages Within D Days

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def canShip(capacity):
            days_needed = 1
            current_load = 0
            for weight in weights:
                if current_load + weight > capacity:
                    days_needed += 1
                    current_load = weight
                else:
                    current_load += weight
            return days_needed <= days
        
        left, right = max(weights), sum(weights)
        while left < right:
            mid = left + (right - left) // 2
            if canShip(mid):
                right = mid
            else:
                left = mid + 1
        return left

Resources

Binary Search Animated - Youtube

Binary Search

Use Cases

Code Template

Initializing search range

Update search range

Implenent valid function

Common mistakes

Issues and consideration

Related Problems

Resources