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.
- 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.
- 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.
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 indexdef first_true(low, high, feasible):
while low < high:
mid = (low + high) // 2
if feasible(mid):
high = mid
else:
low = mid + 1
return lowdef last_true(low, high, feasible):
while low < high:
mid = (low + high + 1) // 2
if feasible(mid):
low = mid
else:
high = mid - 1
return low