Dashboard/Coding patterns/09. Modified Binary Search

CODING PATTERNS · LESSON 9 OF 28 · 72 MIN VIDEO · 24 PROBLEMS

Modified Binary Search

Module Progress (0 / 24 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (72 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Modified Binary Search — How the Pattern Works

Modified Binary Search generalizes classic midpoint halving beyond sorted-array lookups to locate exact targets in piecewise-sorted arrays, find monotonic predicate boundaries, and optimize parameter values directly over discrete or continuous answer spaces. At each iteration, the algorithm maintains an active search interval [low, high] guaranteed to contain the target index or optimal value, evaluating mid against a local structural property or monotonic feasibility test to eliminate half of the remaining candidates. This invariant reduces linear O(n) array scans and O(R) exhaustive value searches to O(log n) or O(log R) probes with O(1) auxiliary space.

WHEN TO USE THIS PATTERN
  • The input array is sorted, rotated sorted, or exhibits a local directional or parity invariant (such as adjacent inequality in peak finding or even-index pairing around a single element).
  • The question asks for the first or last occurrence, insertion index, or transition boundary where a boolean condition flips once from False to True.
  • The problem asks to minimize the maximum or maximize the minimum of a rate, capacity, or partition sum (e.g., subarray limits, eating speed, or station spacing) where candidate feasibility is monotonic.
  • You need the k-th smallest value across a large implicit set (such as pairwise products or missing positive integers) where counting elements <= x runs in O(1) or O(n log m) time.
  • Constraints involve large array lengths (n >= 10^5) or huge numerical answer ranges (up to 10^9–10^14) where linear scanning exceeds time limits.
COMMON INTERVIEW PITFALLS
  • Infinite loop on a two-element interval [low, low + 1] when pairing low = mid with floor division mid = (low + high) // 2; always round up via mid = (low + high + 1) // 2 whenever the True branch sets low = mid.
  • Skipping past the optimal boundary by setting high = mid - 1 when mid satisfies a First-True predicate; if mid can be the first valid answer, keep it inside the active interval with high = mid.
  • Assuming nums[low] <= nums[mid] proves the left half is sorted when duplicate elements exist in rotated arrays; a three-way tie nums[low] == nums[mid] == nums[high] hides the pivot and requires shrinking bounds by 1.
  • Initializing high = len(arr) - 1 instead of len(arr) when counting elements < limit or finding the first 0 in a row that might contain all 1s, causing an off-by-one error on the full-array boundary.
Exact Match & Insertion Search (Closed Interval [low, high])Finding a specific target or its sorted insertion index when every midpoint comparison eliminates mid along with one half.
def binary_search_exact(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # low holds the sorted insertion index
First-True Boundary Search (Minimize Feasible Answer)Finding the smallest index or minimum valid parameter where a monotonic predicate transitions from False to True.
def first_true(low, high, feasible):
    while low < high:
        mid = (low + high) // 2
        if feasible(mid):
            high = mid
        else:
            low = mid + 1
    return low
Last-True Boundary Search (Maximize Feasible Answer)Finding the maximum valid parameter where a monotonic predicate transitions from True to False, using upper-midpoint rounding to prevent two-element stalls.
def last_true(low, high, feasible):
    while low < high:
        mid = (low + high + 1) // 2
        if feasible(mid):
            low = mid
        else:
            high = mid - 1
    return low

01. Binary Search

Optimal Target: O(log n) time · O(1) space

Given an integer array nums sorted in ascending order and an integer target, return the 0-based index of target if it exists in nums, or -1 if it is not present. Your algorithm must run in O(log n) time.

EXAMPLE 1
Input: nums = [-1, 0, 3, 5, 9, 12], target = 5
Output: 3
Explanation: Probing mid = 2 gives nums[2] = 3 < 5 (advance low = 3), probing mid = 4 gives nums[4] = 9 > 5 (move high = 3), and probing mid = 3 matches nums[3] = 5.
EXAMPLE 2
Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
Explanation: The active range narrows until low exceeds high without encountering 2, confirming 2 is absent.
VISUAL INPUT
-1035912
AUTOMATED TEST SUITE
Test Case 1
Input: [-1, 0, 3, 5, 9, 12], 5
Expected: 3
Test Case 2
Input: [-1, 0, 3, 5, 9, 12], 2
Expected: -1
Test Case 3
Input: [], 1
Expected: -1
Python 3.14 Runtime Ready

Click ▶ Run Tests (or press ⌘+Enter) to execute search against all 3 test cases in WebAssembly Python.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

You have a thousand sorted values. In the worst case, about how many looks does binary search need?