all topics

Binary Search

Find target in a sorted array nums, return its index or -1. nums = [-1,0,3,5,9,12], target = 9 → 4.

Halve the search space each time

  • Look at the middle element.
  • Target's smaller → it must be in the left half, search there.
  • Target's bigger → search the right half.
  • Match → return the index. Pointers cross with no match → return -1.
python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l,r = 0, len(nums) - 1
 
        while l<=r:
            m = l + ((r-l) // 2)
 
            if target < nums[m]:
                r = m-1
            elif target > nums[m]:
                l = m+1
            else:
                return m
        return -1
timeO(log n)spaceO(1)

Search Insert Position

Find target in a sorted array nums, or the index where it would be inserted to keep it sorted. nums = [1,3,5,6], target = 5 → 2. target = 2 → 1.

Binary search, l lands on the insertion point

  • Same binary search as usual, narrow the range by comparing nums[mid] to target.
  • Found it → return mid directly.
  • Not found → once l and r cross, l is exactly where target belongs to keep the array sorted.
python
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + ((r-l) // 2)
            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        return l
timeO(log n)spaceO(1)

Guess Number Higher or Lower

A number between 1 and n is picked. guess(num) tells you if your guess is too high (-1), too low (1), or correct (0). Find the number.

Binary search against the guess API

  • Same binary search shape, just using guess(mid) instead of comparing to a known array.
  • guess says too high → search the left half.
  • Too low → search the right half.
  • 0 → found it, return mid.
python
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
# def guess(num: int) -> int:
 
class Solution:
    def guessNumber(self, n: int) -> int:
        l,r = 1,n
        
        while l<=r:
            mid = (l + r) // 2
 
            if guess(mid) == -1:
                r = mid - 1
            elif guess(mid) == 1:
                l = mid + 1
            else:
                return mid
timeO(log n)spaceO(1)

Sqrt(x)

Return the integer square root of x, rounded down. x = 8 → 2 (since 2*2=4 <= 8 < 9=3*3).

Binary search on the answer

  • Search the range [0, x] for the largest number whose square doesn't exceed x.
  • Square too big → search lower.
  • Square too small → search higher, but remember this candidate (res), it might be the answer.
  • Exact square root → return it immediately.
python
class Solution:
    def mySqrt(self, x: int) -> int:
        l, r = 0, x
        res = 0
 
        while l <= r:
            m = l + (r - l) // 2
            if m * m > x:
                r = m - 1
            elif m * m < x:
                l = m + 1
                res = m
            else:
                return m
 
        return res
timeO(log x)spaceO(1)

Search a 2D Matrix

Each row is sorted, and each row's first value is bigger than the previous row's last, so the whole matrix reads as one sorted sequence. Find whether target exists. matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 → True.

Binary search, treat it as one flat array

  • Binary search over indices 0 to m*n - 1, as if the matrix were flattened into a single row.
  • Convert a flat index back to (row, col): row = mid // n, col = mid % n.
  • Compare matrix[row][col] to target and narrow the range as usual.
python
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
 
        t = m * n
        l = 0
        r = t - 1
 
        while l <= r:
            mid = (l + r) // 2
 
            i = mid // n
            j = mid % n
 
            mid_num = matrix[i][j]
 
            if target == mid_num:
                return True
            elif target < mid_num:
                r = mid - 1
            else:
                l = mid + 1
 
        return False
timeO(log(m*n))spaceO(1)

Koko Eating Bananas

Find the minimum eating speed k so Koko finishes all piles within h hours (eating at most one pile per hour, ceil(pile/k) hours per pile). piles = [3,6,7,11], h = 8 → 4.

Binary search on the eating speed

  • Search speeds from 1 to the largest pile.
  • For a candidate speed k, check whether the total hours needed (sum of ceil(pile/k) across all piles) fits within h.
  • Works → try a smaller speed. Doesn't → need a bigger one.
  • Converges on the smallest speed that still works.
python
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def k_works(k):
            hours = 0
 
            for p in piles:
                hours += ceil(p / k)
 
            return hours <= h
 
        l = 1
        r = max(piles)
 
        while l < r:
            k = (l + r) // 2
 
            if k_works(k):
                r = k
            else:
                l = k + 1
 
        return r
timeO(n log m)spaceO(1)

Capacity To Ship Packages Within D Days

Find the smallest ship capacity that gets all weights shipped, in order, within D days. weights = [1,2,3,4,5,6,7,8,9,10], D = 5 → 15.

Binary search on the capacity

  • Search capacities from max(weights) (has to fit the heaviest single package) to sum(weights) (ship everything in one day).
  • For a candidate capacity, simulate loading: pack weights onto the current day until one more would overflow it, then start a new day. Count the days needed.
  • Too many days → capacity's too small, search higher. Fits within D → try a smaller capacity.
python
class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        minCap = max(weights)
        maxCap = sum(weights)
 
        while minCap < maxCap:
            mid = minCap + (maxCap - minCap) // 2
 
            days = 1
            total = 0
 
            for weight in weights:
                if total + weight > mid:
                    days += 1
                    total = 0
 
                total += weight
 
            if days > D:
                minCap = mid + 1
            else:
                maxCap = mid
 
        return minCap
timeO(n log(sum(weights)))spaceO(1)

Find Minimum in Rotated Sorted Array

A sorted array was rotated at some unknown pivot. Find the minimum element. [3,4,5,1,2] → 1.

Binary search, compare against the right end

  • Compare nums[m] to nums[r].
  • nums[m] > nums[r] → the minimum is somewhere to the right of m (this half is still the "rotated" part, the drop-off hasn't happened yet).
  • Otherwise → the minimum is at m or to its left, so keep m in range.
  • Converges on the smallest element.
python
class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        l = 0
        r = n - 1
 
        while l < r:
            m = (l + r) // 2
 
            if nums[m] > nums[r]:
                l = m + 1
            else:
                r = m
 
        return nums[l]
timeO(log n)spaceO(1)

Search in Rotated Sorted Array

A sorted array was rotated at some unknown pivot, all values distinct. Find target's index, or -1. [4,5,6,7,0,1,2], target = 0 → 4.

Find the rotation point, then binary search the right half

  • First binary search: find the index of the minimum element (the rotation point), same technique as Find Minimum in Rotated Sorted Array.
  • That splits the array into two sorted halves. Compare target against the boundary values to figure out which half it could be in.
  • Second binary search: a normal one, just confined to that half.
python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        l = 0
        r = n - 1
 
        # Find the minimum element (rotation point)
        while l < r:
            m = (l + r) // 2
 
            if nums[m] > nums[r]:
                l = m + 1
            else:
                r = m
 
        min_i = l
 
        # Decide which sorted half to search
        if min_i == 0:
            l, r = 0, n - 1
        elif nums[0] <= target <= nums[min_i - 1]:
            l, r = 0, min_i - 1
        else:
            l, r = min_i, n - 1
 
        # Normal binary search
        while l <= r:
            m = (l + r) // 2
 
            if nums[m] == target:
                return m
            elif nums[m] < target:
                l = m + 1
            else:
                r = m - 1
 
        return -1
timeO(log n)spaceO(1)

Search in Rotated Sorted Array II

Same as Search in Rotated Sorted Array, but nums can contain duplicates. Return whether target exists. [2,5,6,0,0,1,2], target = 0 → True.

Binary search, skip duplicates when stuck

  • Found target → done.
  • nums[l] == nums[m] == nums[r] → can't tell which half is sorted, so shrink both ends by one and try again.
  • Otherwise, figure out which half is sorted (same idea as the no-duplicates version) and narrow down accordingly.
  • Duplicates are what make this different: they're also what can degrade it to O(n) in the worst case (e.g. an array of all the same value), instead of the usual O(log n).
python
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        l, r = 0, len(nums) - 1
 
        while l <= r:
            m = (l + r) // 2
 
            if nums[m] == target:
                return True
 
            # Duplicates make it impossible to know
            # which side is sorted
            if nums[l] == nums[m] == nums[r]:
                l += 1
                r -= 1
 
            # Left half is sorted
            elif nums[l] <= nums[m]:
                if nums[l] <= target < nums[m]:
                    r = m - 1
                else:
                    l = m + 1
 
            # Right half is sorted
            else:
                if nums[m] < target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1
 
        return False
timeO(n) worst casespaceO(1)

Find Peak Element

Find any index whose value is strictly greater than both its neighbors (edges compare against -infinity). [1,2,3,1] → 2.

Binary search toward the uphill side

  • A neighbor to the left is bigger → the peak is somewhere to the left, search there.
  • A neighbor to the right is bigger → the peak is somewhere to the right, search there.
  • Neither neighbor is bigger → mid itself is a peak, return it.
python
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l,r = 0, len(nums) - 1
 
        while l<=r:
            mid = l + (r-l) // 2
 
            if mid > 0 and nums[mid-1] > nums[mid]:
                r = mid - 1
            elif mid < len(nums) - 1 and nums[mid+1] > nums[mid]:
                l = mid + 1
            else:
                return mid
timeO(log n)spaceO(1)