Modified Binary Search

Boundaries · Rotation · Peaks

1:00

How one binary search template — with three swappable decision rules — solves first/last occurrence, rotated-array search, and peak-finding all in O(log n).

By the end, you can

Explain why the midpoint formula `lo + (hi - lo) // 2` avoids integer overflow.
Trace the classic binary search loop and count the number of comparisons for a given input.
Modify the template to find the first occurrence of a duplicate target in a sorted array.
Modify the template to find the last occurrence, and derive the count of duplicates from the two indices.
Identify which half of a rotated-array window is sorted and decide which half to discard.
Trace the rotated-array search to the correct index.
Apply the "climb uphill" rule to find a peak element in O(log n) without requiring sorted order.
Explain why all three variations share the same O(log n) time and O(1) space complexity.

Up next in Searching & Sorting