Search in an Almost-Sorted Array

Search in an Almost-Sorted Array takes the cleanest algorithm in the book — binary search — and breaks one assumption: the array is nearly sorted, but any element may have swapped places with one of its neighbors. The fix is a tiny one, and it teaches you to never trust a[mid] alone.

The slow way first

You could just scan every cell — O(n). That always works, but it throws away the structure we were handed. The array is almost sorted, so binary search should still be on the table; we only need to account for the wobble.

The question to ask: if a value can sit one position off, what does landing on mid actually tell me? On its own, a[mid] could be the target's neighbor instead of the target. So I should look a little wider before I commit to throwing away half the array.

The idea: peek a three-cell window

Run a normal binary search, but at each step inspect a window of three cells — a[mid - 1], a[mid], and a[mid + 1] — before deciding where to go. If any of the three equals x, return that index. Otherwise compare x against a[mid] to pick a side, and jump by two (lo = mid + 2 or hi = mid - 2) so we skip the cells we already checked and never re-examine them.

Jumping by two is the crucial detail. We already know the answer is not in any of the three checked cells, so moving to mid + 1 (the usual binary-search step) would re-test a cell we just ruled out. Skipping to mid + 2 keeps the search O(log n) and avoids an infinite loop on tiny ranges.

Walk through it

Step through the animation. lo and hi start at the two ends and mid lands on index 3, value 20. That is not 40, so we peek the neighbors: a[mid - 1] is 40 — the value that slid left when it swapped with the 20. We return mid - 1 = 2 without ever discarding the half that secretly held our answer.

Pseudocode

lo, hi = 0, n - 1
while lo <= hi:
    mid = (lo + hi) // 2
    if a[mid] == x:          return mid
    if mid > lo and a[mid-1] == x:   return mid - 1   # value slid left
    if mid < hi and a[mid+1] == x:   return mid + 1   # value slid right
    if x < a[mid]:           hi = mid - 2             # jump past the window
    else:                    lo = mid + 2
return -1                                              # not present

The Python solution

def search_almost_sorted(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x:
            return mid
        if mid > lo and a[mid - 1] == x:
            return mid - 1
        if mid < hi and a[mid + 1] == x:
            return mid + 1
        if x < a[mid]:
            hi = mid - 2
        else:
            lo = mid + 2
    return -1

• lo and hi bound the part of the array still worth searching, exactly as in plain binary search.
• mid = (lo + hi) // 2 is the center of the current window.
• The first check is the ordinary hit on a[mid].
• The next two checks are the swap-safe peeks: mid > lo and mid < hi guard against reading outside the current window, then we test the left and right neighbor for the target.
• x < a[mid] chooses a direction, and we move hi or lo by two, not one, because the three cells in the window are already ruled out.

Complexity

We still halve the search space every step, so the runtime stays O(log n); the only change is a constant amount of extra peeking. No extra memory is needed — the pointers do all the work.

When this pattern shows up

Practice