Given an integer array nums sorted in ascending order (with distinct values) that has been possibly rotated at an unknown pivot, and an integer target, return the index of target if it is in nums, or -1 if it is not. You must write an algorithm with O(log n) runtime complexity.
nums = [4,5,6,7,0,1,2], target = 04nums = [4,5,6,7,0,1,2], target = 3-1nums = [6,7,0,1,2,4,5], target = 45mid; check if left half is sorted: nums[lo] ≤ nums[mid]target ∈ [nums[lo], nums[mid]) → go left (hi = mid − 1)lo = mid + 1)target ∈ (nums[mid], nums[hi]] → go right (lo = mid + 1)hi = mid − 1)-1 if the loop ends without finding targetEven after rotation, exactly one of the two halves [lo..mid] or [mid..hi] is guaranteed to be sorted in ascending order. By identifying which half is sorted, we can check in O(1) whether the target lies in that sorted range. If yes, we search there; if no, it must be in the other (rotated) half. This eliminates half the remaining elements each iteration, giving O(log n) total time — the same as standard binary search despite the rotation.
A linear scan is O(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.
One half of a rotated array is always sorted. Check if the target fits in the sorted half, and discard the other one.
Run the animation above on your own input, or watch the 1:22 video explanation of Search in Rotated Sorted Array with a dry run and Java code.