Binary Search Patterns 2026: 20+ Problems [Solved]

Last Updated: June 2026

Why Binary Search is Non-Negotiable

Candidates report binary search as appearing in over roughly 20% of FAANG coding rounds. Based on public preparation resources and candidate-reported interview threads, it is one of the highest-ROI topics in placement prep. It has four distinct flavors that interviewers rotate through, and each requires its own template. Getting mid calculation wrong or using the wrong boundary condition costs you the question even when your logic is correct.

This guide gives you the exact templates for all four variants plus 20+ solved problems.

The Four Patterns

1. CLASSIC: Find target in sorted array → O(log n)
2. BOUNDARY: First/last occurrence, lower/upper bound
3. ROTATED: Sorted array rotated at unknown pivot
4. ANSWER SPACE: Binary search on the answer, not the array

Pattern 1: Classic Binary Search

def binary_search(arr, target):
    """
    Classic search. Returns index or -1.
    Time: O(log n)  Space: O(1)

    INVARIANT: arr[left] <= target <= arr[right]
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2  # avoid overflow

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Key rule: left <= right (not <) because we need to check when left == right.

Pattern 2: Lower Bound (First Occurrence)

def lower_bound(arr, target):
    """
    Returns leftmost index where arr[i] >= target.
    If all elements < target, returns len(arr).
    Time: O(log n)  Space: O(1)
    """
    left, right = 0, len(arr)  # right = len(arr), not len(arr)-1

    while left < right:             # not <=
        mid = left + (right - left) // 2

        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid             # not mid - 1

    return left  # left == right == answer


def first_occurrence(arr, target):
    """Find first index where arr[i] == target."""
    idx = lower_bound(arr, target)
    if idx < len(arr) and arr[idx] == target:
        return idx
    return -1

Pattern 3: Upper Bound (Last Occurrence)

def upper_bound(arr, target):
    """
    Returns leftmost index where arr[i] > target.
    Last occurrence of target = upper_bound(target) - 1.
    Time: O(log n)  Space: O(1)
    """
    left, right = 0, len(arr)

    while left < right:
        mid = left + (right - left) // 2

        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid

    return left


def last_occurrence(arr, target):
    idx = upper_bound(arr, target) - 1
    if idx >= 0 and arr[idx] == target:
        return idx
    return -1

Practice Questions with Solutions

Problem 1: Search Insert Position (EASY)

Asked at: Amazon, Microsoft, TCS

Problem: Given sorted array and target, return index if found, or where it would be inserted to maintain order.

def search_insert(nums, target):
    """
    Lower bound = first position where nums[i] >= target.
    Time: O(log n)  Space: O(1)
    """
    left, right = 0, len(nums)

    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid

    return left

# Example
print(search_insert([1, 3, 5, 6], 5))  # 2
print(search_insert([1, 3, 5, 6], 2))  # 1
print(search_insert([1, 3, 5, 6], 7))  # 4

Complexity: Time O(log n), Space O(1)

Problem 2: Find First and Last Position (MEDIUM)

Asked at: Amazon, Google, Microsoft, Flipkart

Problem: Find the starting and ending position of a target in a sorted array.

def search_range(nums, target):
    """
    Use lower_bound and upper_bound.
    Time: O(log n)  Space: O(1)
    """
    def lower_bound(arr, t):
        lo, hi = 0, len(arr)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if arr[mid] < t:
                lo = mid + 1
            else:
                hi = mid
        return lo

    first = lower_bound(nums, target)
    if first == len(nums) or nums[first] != target:
        return [-1, -1]

    last = lower_bound(nums, target + 1) - 1
    return [first, last]

# Example
print(search_range([5, 7, 7, 8, 8, 10], 8))   # [3, 4]
print(search_range([5, 7, 7, 8, 8, 10], 6))   # [-1, -1]

Complexity: Time O(log n), Space O(1)

Problem 3: Search in Rotated Sorted Array (MEDIUM)

Asked at: Amazon, Google, Microsoft, Uber - very frequently asked

Problem: Array was sorted then rotated at some pivot. Find target.

def search_rotated(nums, target):
    """
    Key insight: one half is always sorted after each mid check.
    Determine which half is sorted, then check if target falls in it.
    Time: O(log n)  Space: O(1)
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

# Example
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))  # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))  # -1

Complexity: Time O(log n), Space O(1)

Problem 4: Find Minimum in Rotated Sorted Array (MEDIUM)

Asked at: Amazon, Google, Goldman Sachs

Problem: Find the minimum element in a rotated sorted array.

def find_min_rotated(nums):
    """
    The minimum is the only element smaller than its predecessor.
    Left boundary of the unsorted segment.
    Time: O(log n)  Space: O(1)
    """
    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] > nums[right]:
            # Minimum is in right half
            left = mid + 1
        else:
            # Minimum is in left half (including mid)
            right = mid

    return nums[left]

# Example
print(find_min_rotated([3, 4, 5, 1, 2]))      # 1
print(find_min_rotated([4, 5, 6, 7, 0, 1, 2]))  # 0

Complexity: Time O(log n), Space O(1)

Problem 5: Peak Element (MEDIUM)

Asked at: Google, Amazon, Facebook

Problem: Find a peak element. An element is a peak if greater than its neighbors. Array may have multiple peaks; return any.

def find_peak_element(nums):
    """
    Binary search: if nums[mid] < nums[mid+1], peak is on right.
    Otherwise peak is on left (including mid).
    Time: O(log n)  Space: O(1)
    """
    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] < nums[mid + 1]:
            left = mid + 1
        else:
            right = mid

    return left

# Example
print(find_peak_element([1, 2, 3, 1]))      # 2 (nums[2]=3 is peak)
print(find_peak_element([1, 2, 1, 3, 5, 6, 4]))  # 5 (one valid peak)

Complexity: Time O(log n), Space O(1)

Problem 6: Koko Eating Bananas - Answer Space Binary Search (MEDIUM)

Asked at: Amazon, Google, Uber

Problem: Koko eats k bananas per hour. Find minimum k such that she can eat all piles within h hours.

def min_eating_speed(piles, h):
    """
    Answer space: k in [1, max(piles)].
    Check feasibility: can Koko eat all piles at speed k in h hours?
    Binary search on k.
    Time: O(n log m) where m = max(piles)  Space: O(1)
    """
    import math

    def can_finish(speed):
        hours = sum(math.ceil(p / speed) for p in piles)
        return hours <= h

    left, right = 1, max(piles)

    while left < right:
        mid = left + (right - left) // 2
        if can_finish(mid):
            right = mid       # feasible, try smaller
        else:
            left = mid + 1    # not feasible, need larger

    return left

# Example
print(min_eating_speed([3, 6, 7, 11], 8))   # 4
print(min_eating_speed([30, 11, 23, 4, 20], 5))  # 30

Complexity: Time O(n log m), Space O(1)

Problem 7: Minimum Days to Make Bouquets - Answer Space (MEDIUM)

Asked at: Amazon, Google

Problem: Given bloom day for each flower, k flowers per bouquet, m bouquets needed. Find minimum day to make m bouquets using k adjacent flowers.

def min_days(bloom_day, m, k):
    """
    Binary search on answer (day number).
    Feasibility: can we make m bouquets on day `d`?
    Time: O(n log n)  Space: O(1)
    """
    if m * k > len(bloom_day):
        return -1

    def can_make(day):
        bouquets = 0
        flowers = 0
        for b in bloom_day:
            if b <= day:
                flowers += 1
                if flowers == k:
                    bouquets += 1
                    flowers = 0
            else:
                flowers = 0
        return bouquets >= m

    left, right = min(bloom_day), max(bloom_day)

    while left < right:
        mid = left + (right - left) // 2
        if can_make(mid):
            right = mid
        else:
            left = mid + 1

    return left

# Example
print(min_days([1, 10, 3, 10, 2], 3, 1))  # 3
print(min_days([1, 10, 3, 10, 2], 3, 2))  # -1

Complexity: Time O(n log n), Space O(1)

Problem 8: Capacity to Ship Packages - Answer Space (MEDIUM)

Asked at: Amazon, Google, Uber

Problem: Given weights and D days, find minimum ship capacity to ship all packages within D days. Packages must be shipped in order.

def ship_within_days(weights, days):
    """
    Answer: capacity in [max(weights), sum(weights)].
    Feasibility: can we ship all packages in `days` days with given capacity?
    Time: O(n log n)  Space: O(1)
    """
    def can_ship(capacity):
        current_load = 0
        days_needed = 1
        for w in weights:
            if current_load + w > capacity:
                days_needed += 1
                current_load = 0
            current_load += w
        return days_needed <= days

    left, right = max(weights), sum(weights)

    while left < right:
        mid = left + (right - left) // 2
        if can_ship(mid):
            right = mid
        else:
            left = mid + 1

    return left

# Example
print(ship_within_days([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))  # 15
print(ship_within_days([3, 2, 2, 4, 1, 4], 3))                 # 6

Complexity: Time O(n log n), Space O(1)

Problem 9: Find K Closest Elements (MEDIUM)

Asked at: Google, Amazon, LinkedIn

Problem: Given sorted array, integer k and x, find k closest elements to x. Return sorted.

def find_closest_elements(arr, k, x):
    """
    Binary search for left boundary of the window of size k.
    Key: prefer the left element when equidistant.
    Time: O(log(n-k) + k)  Space: O(1)
    """
    left, right = 0, len(arr) - k

    while left < right:
        mid = left + (right - left) // 2
        # Compare distances: left boundary arr[mid] vs right boundary arr[mid+k]
        if x - arr[mid] > arr[mid + k] - x:
            left = mid + 1
        else:
            right = mid

    return arr[left:left + k]

# Example
print(find_closest_elements([1, 2, 3, 4, 5], 4, 3))   # [1, 2, 3, 4]
print(find_closest_elements([1, 2, 3, 4, 5], 4, -1))  # [1, 2, 3, 4]

Complexity: Time O(log(n-k) + k), Space O(1)

Problem 10: Sqrt(x) - Integer Square Root (EASY)

Asked at: Amazon, Google, TCS, Infosys

Problem: Compute integer square root of x without using sqrt().

def my_sqrt(x):
    """
    Binary search in [0, x]. Find largest k where k^2 <= x.
    Time: O(log x)  Space: O(1)
    """
    if x < 2:
        return x

    left, right = 1, x // 2

    while left <= right:
        mid = left + (right - left) // 2
        if mid * mid == x:
            return mid
        elif mid * mid < x:
            left = mid + 1
        else:
            right = mid - 1

    return right  # right is floor(sqrt(x))

# Example
print(my_sqrt(4))   # 2
print(my_sqrt(8))   # 2 (floor of 2.828...)

Complexity: Time O(log x), Space O(1)

Problem 11: Search a 2D Matrix (MEDIUM)

Asked at: Amazon, Microsoft, Google

Problem: Matrix where each row is sorted and first element of each row is greater than last of previous row. Search for target.

def search_matrix(matrix, target):
    """
    Treat 2D matrix as 1D sorted array.
    Index mapping: matrix[idx // cols][idx % cols]
    Time: O(log(m*n))  Space: O(1)
    """
    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1

    while left <= right:
        mid = left + (right - left) // 2
        val = matrix[mid // n][mid % n]

        if val == target:
            return True
        elif val < target:
            left = mid + 1
        else:
            right = mid - 1

    return False

# Example
print(search_matrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 3))   # True
print(search_matrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 13))  # False

Complexity: Time O(log(m*n)), Space O(1)

Problem 12: Allocate Minimum Pages (HARD)

Asked at: Amazon, Flipkart, Google - classic answer-space binary search

Problem: Allocate n books to m students such that maximum pages allocated to a student is minimized.

def allocate_min_pages(pages, m):
    """
    Answer space: [max(pages), sum(pages)].
    Feasibility: can we allocate with max pages = limit using at most m students?
    Time: O(n log(sum))  Space: O(1)
    """
    if m > len(pages):
        return -1

    def is_feasible(limit):
        students = 1
        current = 0
        for p in pages:
            if p > limit:
                return False
            if current + p > limit:
                students += 1
                current = p
            else:
                current += p
        return students <= m

    left, right = max(pages), sum(pages)

    while left < right:
        mid = left + (right - left) // 2
        if is_feasible(mid):
            right = mid
        else:
            left = mid + 1

    return left

# Example
print(allocate_min_pages([12, 34, 67, 90], 2))  # 113 (books [12,34,67] and [90])

Complexity: Time O(n log n), Space O(1)

Problem 13: Median of Two Sorted Arrays (HARD)

Asked at: Google, Amazon, Facebook, Microsoft - O(log(min(m,n))) required

Problem: Find median of two sorted arrays in O(log(min(m,n))).

def find_median_sorted_arrays(nums1, nums2):
    """
    Binary search on partition of smaller array.
    Time: O(log(min(m,n)))  Space: O(1)
    """
    A, B = nums1, nums2
    if len(A) > len(B):
        A, B = B, A

    m, n = len(A), len(B)
    total = m + n
    half = total // 2

    left, right = 0, m

    while left <= right:
        i = (left + right) // 2   # partition of A
        j = half - i              # partition of B

        A_left  = A[i - 1] if i > 0 else float('-inf')
        A_right = A[i]     if i < m else float('inf')
        B_left  = B[j - 1] if j > 0 else float('-inf')
        B_right = B[j]     if j < n else float('inf')

        if A_left <= B_right and B_left <= A_right:
            if total % 2:
                return min(A_right, B_right)
            return (max(A_left, B_left) + min(A_right, B_right)) / 2
        elif A_left > B_right:
            right = i - 1
        else:
            left = i + 1

# Example
print(find_median_sorted_arrays([1, 3], [2]))      # 2.0
print(find_median_sorted_arrays([1, 2], [3, 4]))   # 2.5

Complexity: Time O(log(min(m,n))), Space O(1)

Decision Tree: Which Template to Use?

Is the array sorted?
    NO  → might not be binary search; check answer-space variant
    YES → continue

Are duplicates present?
    YES, need first/last → use lower_bound / upper_bound
    NO or any occurrence fine → use classic template

Is the array rotated?
    YES → use rotated array template
    NO  → classic or boundary

Is it a min/max optimization problem?
    "Minimum possible X such that condition holds" or
    "Maximum possible X such that condition holds"
    YES → Binary search on answer space
         Check: is the feasibility function monotone?
         left = min answer, right = max answer

Complexity Summary

The Single Most Common Bug

# WRONG - integer overflow in large inputs
mid = (left + right) // 2

# RIGHT - safe in all languages
mid = left + (right - left) // 2

Python does not overflow integers, but this habit is mandatory in Java/C++ interviews.

Related Articles

• Dynamic Programming Patterns 2026
• Arrays Questions Placement
• Two Pointers Pattern Questions 2026
• Must-Do Coding Questions
• System Design Interview Questions 2026