Plain binary search needs a sorted array. Interviewers rarely give you one. Instead they hand you an array that is almost sorted — rotated at an unknown pivot, or shaped like a mountain, or sorted along rows and columns of a matrix.

The unifying idea is broader than “sorted”:

Binary search works whenever you can look at midmid and discard half the search space with certainty.

Sortedness is just the most familiar reason you can do that. This page covers the three other reasons that show up constantly.

What you’ll learn

• The “which half is sorted” test that handles rotation.
• Why lo < hilo < hi with hi = midhi = mid is the right loop shape for minimum/peak-finding, and lo <= hilo <= hi with mid ± 1mid ± 1 for exact search.
• Peak finding: binary search with no sortedness at all, just a local gradient.
• The staircase walk for row/column-sorted matrices — $O(m + n)$, and not a binary search at all.
• Three real LeetCode problems solved in the browser: 33, 153, 162.

The cue

Pattern 1 — rotated array, exact search

In a rotated sorted array, at least one half around midmid is always properly sorted. Identify which, then check whether the target lies inside that sorted half: if yes, search it; if no, search the other.

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:                             # exact search shape
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
 
        if nums[lo] <= nums[mid]:               # LEFT half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1                    # target is in the sorted left
            else:
                lo = mid + 1
        else:                                   # RIGHT half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1                    # target is in the sorted right
            else:
                hi = mid - 1
 
    return -1
 
 
print(search([4, 5, 6, 7, 0, 1, 2], 0))   # 4
print(search([4, 5, 6, 7, 0, 1, 2], 3))   # -1

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:                             # exact search shape
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
 
        if nums[lo] <= nums[mid]:               # LEFT half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1                    # target is in the sorted left
            else:
                lo = mid + 1
        else:                                   # RIGHT half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1                    # target is in the sorted right
            else:
                hi = mid - 1
 
    return -1
 
 
print(search([4, 5, 6, 7, 0, 1, 2], 0))   # 4
print(search([4, 5, 6, 7, 0, 1, 2], 3))   # -1

Duplicates break the guarantee. In LC 81, nums[lo] == nums[mid]nums[lo] == nums[mid] no longer tells you which side is sorted — consider [1,1,1,0,1][1,1,1,0,1]. The fix is to shrink one step (lo += 1lo += 1) when nums[lo] == nums[mid] == nums[hi]nums[lo] == nums[mid] == nums[hi], which makes the worst case $O(n)$. That degradation is unavoidable, and saying so is the expected answer.

Pattern 2 — find the rotation point (minimum)

Here you want a position, not a value match, so use the lo < hilo < hi shape. Compare nums[mid]nums[mid] against nums[hi]nums[hi]:

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:                       # boundary-finding shape
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1                 # minimum is strictly to the right
        else:
            hi = mid                     # mid could BE the minimum
    return nums[lo]
 
 
print(find_min([3, 4, 5, 1, 2]))       # 1
print(find_min([11, 13, 15, 17]))      # 11  (not rotated at all)

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:                       # boundary-finding shape
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1                 # minimum is strictly to the right
        else:
            hi = mid                     # mid could BE the minimum
    return nums[lo]
 
 
print(find_min([3, 4, 5, 1, 2]))       # 1
print(find_min([11, 13, 15, 17]))      # 11  (not rotated at all)

Compare with nums[hi]nums[hi], not nums[lo]nums[lo]. Against nums[lo]nums[lo] the not-rotated case ([11,13,15,17][11,13,15,17]) is ambiguous and needs a special case; against nums[hi]nums[hi] it falls out correctly with no extra branch.

Pattern 3 — peak finding, with no sortedness at all

LC 162 gives an array where neighbours differ, and asks for any index whose value is greater than both neighbours. The array is not sorted in any sense. Binary search still works:

def find_peak_element(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1                 # we are ascending: a peak lies right
        else:
            hi = mid                     # descending: mid may be the peak
    return lo
 
 
print(find_peak_element([1, 2, 1, 3, 5, 6, 4]))   # 5 (or 1 -- both are peaks)

def find_peak_element(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1                 # we are ascending: a peak lies right
        else:
            hi = mid                     # descending: mid may be the peak
    return lo
 
 
print(find_peak_element([1, 2, 1, 3, 5, 6, 4]))   # 5 (or 1 -- both are peaks)

Why it is guaranteed to find one: if nums[mid] < nums[mid+1]nums[mid] < nums[mid+1], the segment to the right starts by ascending, and since the array ends (treat the out-of-bounds neighbours as $-\infty$), it must turn down somewhere — so a peak exists in [mid+1, hi][mid+1, hi]. The same argument mirrors on the other side. The invariant “the current range contains a peak” is preserved, and the range shrinks every step.

This is the clearest demonstration that binary search is about discarding half with certainty, not about sorted data.

Pattern 4 — sorted matrices are two different problems

def search_matrix_ii(matrix, target):
    if not matrix or not matrix[0]:
        return False
    row, col = 0, len(matrix[0]) - 1        # start top-RIGHT
    while row < len(matrix) and col >= 0:
        value = matrix[row][col]
        if value == target:
            return True
        if value > target:
            col -= 1                        # this whole column is too big
        else:
            row += 1                        # this whole row is too small
    return False

def search_matrix_ii(matrix, target):
    if not matrix or not matrix[0]:
        return False
    row, col = 0, len(matrix[0]) - 1        # start top-RIGHT
    while row < len(matrix) and col >= 0:
        value = matrix[row][col]
        if value == target:
            return True
        if value > target:
            col -= 1                        # this whole column is too big
        else:
            row += 1                        # this whole row is too small
    return False

The variant map

Practice — real LeetCode problems

LC 33 — Search in Rotated Sorted Array · Medium

Problem. An ascending array with distinct values was rotated at an unknown pivot. Given the rotated array and a targettarget, return its index, or -1-1. You must write an $O(\log n)$ algorithm.

Constraints. 1 <= len(nums) <= 50001 <= len(nums) <= 5000, all values unique, -10^4 <= nums[i], target <= 10^4-10^4 <= nums[i], target <= 10^4.

Examples. nums = [4,5,6,7,0,1,2], target = 0nums = [4,5,6,7,0,1,2], target = 0 gives 44 · target = 3target = 3 gives -1-1 · nums = [1], target = 0nums = [1], target = 0 gives -1-1

LC 153 — Find Minimum in Rotated Sorted Array · Medium

Problem. An ascending array of unique elements was rotated. Return its minimum element in $O(\log n)$.

Constraints. 1 <= len(nums) <= 50001 <= len(nums) <= 5000, all values unique. The array may not actually be rotated.

Examples. [3,4,5,1,2][3,4,5,1,2] gives 11 · [4,5,6,7,0,1,2][4,5,6,7,0,1,2] gives 00 · [11,13,15,17][11,13,15,17] gives 1111

LC 162 — Find Peak Element · Medium

Problem. A peak element is strictly greater than its neighbours. Given an array where nums[i] != nums[i+1]nums[i] != nums[i+1] for all valid ii, return the index of any peak. Imagine nums[-1]nums[-1] and nums[n]nums[n] are $-\infty$. Must be $O(\log n)$.

Constraints. 1 <= len(nums) <= 10001 <= len(nums) <= 1000, adjacent elements always differ.

Examples. [1,2,3,1][1,2,3,1] gives 22 · [1,2,1,3,5,6,4][1,2,1,3,5,6,4] gives 55 or 11 — both are peaks

LeetCode problem set

Interview follow-ups

Edge-case checklist

• Single element — every template must handle len == 1len == 1.
• Two elements — [3,1][3,1] for LC 33 (the <=<= test) and [2,1][2,1] for LC 153.
• Not actually rotated — [11,13,15,17][11,13,15,17]; the reason to compare with nums[hi]nums[hi].
• Rotated by exactly one — [5,1,2,3,4][5,1,2,3,4] and [2,3,4,5,1][2,3,4,5,1].
• Target absent — must return -1-1, not the nearest index.
• Target at the pivot — both the minimum and the element before it.
• Monotonic input for peak-finding — [1,2,3,4,5][1,2,3,4,5] peaks at the last index, [5,4,3,2,1][5,4,3,2,1] at the first; both exercise the $-\infty$ boundary.
• Empty matrix — guard matrixmatrix and matrix[0]matrix[0] before indexing.
• mid + 1mid + 1 in range — only safe under the lo < hilo < hi shape.

Recap

• Binary search needs only that you can discard half with certainty — not that the data is sorted.
• Rotated exact search: find the sorted half with nums[lo] <= nums[mid]nums[lo] <= nums[mid] (the <=<= matters), then test whether the target lies inside it.
• Two loop shapes: lo <= hilo <= hi with mid ± 1mid ± 1 to find a value; lo < hilo < hi with hi = midhi = mid to find a boundary, minimum, or peak. Never mix them.
• Rotation point: compare nums[mid]nums[mid] with nums[hi]nums[hi], which handles the un-rotated array without a special case.
• Peak finding works on unsorted data via the local gradient, and the invariant “this range contains a peak”.
• Duplicates cost you the guarantee and degrade the worst case to $O(n)$ — say so rather than pretending otherwise.
• Sorted matrices split in two: fully sorted means $O(\log mn)$; row/column sorted means an $O(m+n)$ staircase from the top-right.

Next: Binary Search on Answer — searching a space of candidate answers rather than array indices.