Peaks and pairs: testing a neighbour
When the array is not sorted, compare an element with its neighbour instead of with a target. The slope, or the way pairs line up, switches exactly once.
Compare with the neighbour
A mountain array rises to a single peak and then falls. "Is a[i] greater than a[i + 1]?" is false on the way up and true on the way down, so the peak is the first true. Nothing is compared with a target; the test only asks which way the ground slopes at i.
The first index where the array starts to fall.
-
Step 1 / 5lo0hi8
The peak is somewhere in [0, n − 1]. At each step, look at the slope between mid and mid + 1.
-
Step 2 / 5lo0mid4hi8
a[4] = 20 > a[5] = 18. Going down: the peak is 4 or to its left, hi = 4.
-
Step 3 / 5lo0mid2hi4
a[2] = 9 < a[3] = 15. Still climbing: the peak is to the right, lo = 3.
-
Step 4 / 5lo3mid3hi4
a[3] = 15 < a[4] = 20. Still climbing: the peak is to the right, lo = 4.
-
Step 5 / 5answer4
lo = hi = 4: a[4] = 20 is the top of the mountain.
The same idea finds a peak in any array whose neighbours differ, not only a mountain: walk towards the higher neighbour and you must reach a local peak, because you cannot climb for ever. The search halves the range each time and returns one peak, not necessarily the highest.
Searching a mountain for a value
A mountain is two sorted runs back to back, one rising and one falling. Find the peak, then search each run with an ordinary binary search (the falling run with its comparison reversed). Three searches, so O(log n) reads, which is what Find a value in a mountain array asks for when every read is expensive. Search the rising run first: if the value appears on both sides, the smaller index is there.
Pairs that shift
A sorted array in which every value appears twice except one. Before the single value, each pair starts at an even index: (0, 1), (2, 3), … After it, the pairs have shifted by one and start at odd indices. So at an even index i the test "a[i] differs from a[i + 1]" is false before the single value and true from it onwards.
The first even index whose pair is broken.
-
Step 1 / 4lo0hi8
Test at even indices only: does a[i] differ from a[i + 1]? It fails before the single value and passes from it onwards.
-
Step 2 / 4lo0mid4hi8
a[4] = 8 and a[5] = 10: they differ, so the single value is at 4 or before: hi = 4.
-
Step 3 / 4lo0mid2hi4
a[2] = 6 and a[3] = 6: a pair starting at an even index, so everything up to 3 is paired normally: lo = 4.
-
Step 4 / 4answer8
lo = hi = 4: the value without a partner is 8.
The XOR of every element also finds the single value, but it reads all n elements. The question asks for O(log n), which only the parity argument gives.