Search in Rotated Sorted Array
Search in Rotated Sorted Array is a medium Binary Search problem from the Blind 75. The key pattern is binary search on the sorted half, and a good solution runs in O(log n) time.
Problem
Return the index of target in a rotated strictly increasing array, or -1 when absent.
Examples
Example 1
Input
{"nums":[40,50,5,10,20,30],"target":20}Output
4Example 2
Input
{"nums":[7,8,9,1,3,5],"target":1}Output
3Example 3
Input
{"nums":[1],"target":0}Output
-1Approach
At each step one half around the middle is sorted. Search that half if the target falls inside its range, otherwise search the other half.
| Pattern | Binary search on the sorted half |
|---|---|
| Time | O(log n) |
| Space | O(1) |
Watch out for
Use inclusive comparisons on the sorted half's endpoints so targets at the edges are found.