Binary Search

When the search space is sorted or monotonic, binary search finds the answer in O(log n). The key is identifying what to search on — not always the array itself ("search on answer" problems).

// Universal Template

def binary_search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:                         # ← note: <= not <
        mid = l + (r - l) // 2           # avoids overflow
        if nums[mid] == target: return mid
        elif nums[mid] < target: l = mid + 1
        else: r = mid - 1
    return -1

Easy Binary Search

INSIGHT: The template above. Use l + (r-l)//2 to avoid integer overflow (important in Java/C++).

def search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = l + (r - l) // 2
        if nums[mid] == target: return mid
        elif nums[mid] < target: l = mid + 1
        else: r = mid - 1
    return -1
# Time: O(log n) | Space: O(1)

Medium Koko Eating Bananas

INSIGHT: "Search on Answer": search on speed k (1 to max(piles)). Check if speed k is feasible. Find minimum feasible k.

import math

def minEatingSpeed(piles, h):
    l, r = 1, max(piles)
    result = r
    while l <= r:
        k = (l + r) // 2
        hours = sum(math.ceil(p / k) for p in piles)
        if hours <= h:       # valid: try slower
            result = k; r = k - 1
        else:                # too slow: increase k
            l = k + 1
    return result
# Time: O(n log m) where m=max(piles) | Space: O(1)

Medium Find Minimum In Rotated Sorted Array

INSIGHT: If nums[mid] > nums[r], the rotation point (min) is in the right half. Otherwise it's at mid or left.

def findMin(nums):
    l, r = 0, len(nums) - 1
    while l < r:             # ← note: < not <=
        mid = (l + r) // 2
        if nums[mid] > nums[r]:
            l = mid + 1      # min is right of mid
        else:
            r = mid          # mid could be min
    return nums[l]
# Time: O(log n) | Space: O(1)

Medium Search In Rotated Sorted Array

INSIGHT: One half is always sorted. Determine which half, check if target falls within it, go that direction.

def search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target: return mid
        # Left half is sorted
        if nums[l] <= nums[mid]:
            if nums[l] <= target < nums[mid]: r = mid - 1
            else: l = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[r]: l = mid + 1
            else: r = mid - 1
    return -1
# Time: O(log n) | Space: O(1)

Hard Median of Two Sorted Arrays

INSIGHT: Binary search on partition point in smaller array. Ensure max(left1, left2) ≤ min(right1, right2). O(log(min(m,n))).

def findMedianSortedArrays(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1  # ensure nums1 is smaller
    m, n = len(nums1), len(nums2)
    half = (m + n) // 2
    l, r = 0, m
    while True:
        i = (l + r) // 2  # partition in nums1
        j = half - i        # partition in nums2
        l1 = nums1[i-1] if i > 0 else float('-inf')
        r1 = nums1[i]   if i < m else float('inf')
        l2 = nums2[j-1] if j > 0 else float('-inf')
        r2 = nums2[j]   if j < n else float('inf')
        if l1 <= r2 and l2 <= r1:
            if (m+n) % 2: return min(r1, r2)
            return (max(l1,l2) + min(r1,r2)) / 2
        elif l1 > r2: r = i - 1
        else: l = i + 1
# Time: O(log(min(m,n))) | Space: O(1)

← Sliding Window Stack →