Binary Search

Decision Flow

Interactive Flow with Problem Details (Auto-Layout)

Layout:

📍 Manual Layout (Drag nodes to adjust)

🏷️ Keywords

First/Last occurrence

Find the minimum

Minimize the maximum

Non-decreasing order

Sorted in ascending order

React Flow

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:

Use Code Template

69. Sqrt(x)

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

        left = 1
        right = x + 1
        while left < right:
            mid = (left + right) // 2
            if valid(mid):
                right = mid
            else:
                left = mid + 1
        # left - 1 is the index of first non valid() element
        return left - 1

278. First Bad Version

class Solution:
    def firstBadVersion(self, n):
        def valid(mid):
            return isBadVersion(mid)

        left = 0
        right = n + 1
        while left < right:
            mid = (left + right) // 2
            if valid(mid):
                right = mid
            else:
                left = mid + 1
        return left

744. Find Smallest Letter Greater Than Target

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        def valid(letter):
            if letter > target:
                return True
            return False

        left, right = 0, len(letters)
        while left < right:
            mid = (left + right) // 2
            if valid(letters[mid]):
                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:
        def valid(k):
            hours_needed = 0
            for pile in piles:
                hours_needed += (pile + k - 1) // k
            return hours_needed <= h

        left, right = 1, max(piles)
        while left < right:
            mid = (left + right) // 2
            if valid(mid):
                right = mid
            else:
                left = mid + 1
        return left

1011. Capacity To Ship Packages Within D Days

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def valid(capacity):
            days_needed = 1
            current_load = 0
            for weight in weights:
                if current_laoad + 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) // 2
            if valid(mid):
                right = mid
            else:
                left = mid + 1
        return left

1060. Missing Element in Sorted Array

class Solution:
    def missingElement(self, nums, k):
        # n of missicg on left of index >= k
        def valid(index):
            missing = nums[index] - (nums[0] + index)
            if missing >= k:
                return True
            return False
        
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if valid(mid):
                right = mid
            else:
                left = mid + 1
        return nums[0] + left - 1 + k

Common mistakes

Incorrect Loop Condition

# Wrong
while left <= right:  # the valid range is [left, right) in this template
# Correct 
while left < right:

Incorrect Right Boundary Value

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

Incorrect Pointer Updates

# Wrong: missing +1 when updating left
if not valid(nums[mid]):
    left = mid  # This can lead to infinite loop
# Wrong: adding +1 when updating right
if valid(nums[mid]):
    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.

Resources

Binary Search Animated - Youtube