Modified Binary Search

Foundations

In the first lesson, the whole range was sorted, so the middle value alone said which half to drop. Now, what if the sorted order has been rotated, so it climbs, drops once, and climbs again?

Sort nums = [7, 1, 5, 3, 6] into [1, 3, 5, 6, 7], then rotate it by 2, moving the first two values to the back: [5, 6, 7, 1, 3]. It is no longer sorted as a whole, but any split at mid leaves at least one sorted half, because the one drop, from 7 to 1, can sit on only one side. If nums[lo] <= nums[mid], the left half is sorted; otherwise the right half is.

In [5, 6, 7, 1, 3], look for 3 with lo = 0 and hi = 4. mid = 2 holds 7, and 5 <= 7, so the left half [5, 6, 7] is sorted; 3 is not between 5 and 7, so lo = 3. Now mid = 3 holds 1, and 3 is not below it, so lo = 4, where 3 sits. Every step still halves the range.

Case Scenario

Search in Rotated Sorted Array gives a rotated nums and a target: return the target's index, or -1. In nums = [4, 5, 6, 7, 0, 1, 2], the first mid holds 7, and the left half from 4 to 7 is sorted, but 0 is outside it, so the search keeps the right half; 0 turns up at index 4.

The direct approach scans every value, which works on any order and ignores the order this array still has: O(n) comparisons, 5 of them to reach 0 here. Plain binary search fails too, because nums[mid] alone no longer says which side holds the target: 7 is bigger than 0, yet 0 sits to its right.