Search in Rotated Sorted Array
Problem Description
An integer array nums sorted in ascending order is possibly rotated at an unknown pivot. Given the array after rotation and a target, return the index of target, or -1 if not found. Must run in O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
DE Shaw Tier 2 — LC 33.
Binary search: at each mid, one half is always sorted. Check if target is in the sorted half — if yes, search there; if no, search the other half.
Key insight: if nums[lo] <= nums[mid], left half is sorted. Else right half is sorted.
Example Test Cases
Example 1
Input: [[4,5,6,7,0,1,2],0]
Expected: 4
Example 2
Input: [[4,5,6,7,0,1,2],3]
Expected: -1
Example 3
Input: [[1],0]
Expected: -1
Example 4
Input: [[1,3],3]
Expected: 1
Run your code to see the results