A sorted array of distinct numbers was rotated at an unknown point. Return the index of the target, or minus 1, in O of log n time.
DSA Animator › DSA Revision › Binary Search › Search in Rotated Sorted Array
Remember: one half of a rotated array is always sorted. Check if the target fits in the sorted half, and discard the other one. The video solves Search in Rotated Sorted Array (LeetCode 33, Medium) with the Binary Search pattern from the Binary Search topic, and you can replay every step in the interactive Search in Rotated Sorted Array animation.
A sorted array of distinct numbers was rotated at an unknown point. Return the index of the target, or minus 1, in O of log n time.
For 4, 5, 6, 7, 0, 1, 2 and target 0, the answer is index 4.
A linear scan is O of n. Normal binary search fails, because the whole array is not sorted.
Cut at mid, and at least one of the two halves is still sorted. Check if the left half is sorted by comparing the value at low with the value at mid. If the target lies inside the sorted half, search there. Otherwise, search the other half.
Low 0, high 6, mid 3 holds 7. The left half 4 to 7 is sorted, but 0 is not inside it, so low becomes 4. Mid 5 holds 1, and the left part 0 to 1 is sorted and contains 0, so high becomes 4. Mid 4 holds 0, which is the target, so the answer is 4.
In code, return mid on a match. If the value at low is at most the value at mid, the left half is sorted, so check if the target is inside it. Otherwise the right half is sorted, so check that range instead. Each step drops half, so it's O of log n time.
Remember: one half of a rotated array is always sorted. Check if the target fits in the sorted half, and discard the other one.