Search in Rotated Sorted Array

Share

Given a rotated sorted array of unique integers 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

Solution Approach

Binary search with rotation handling: at each step determine which half is sorted, then check if target falls in that sorted half.

  • If nums[mid]==target return mid.
  • If left half [lo..mid] is sorted (nums[lo]<=nums[mid]):
  • If target in [nums[lo], nums[mid]), search left; else search right.
  • Else right half [mid..hi] is sorted:
  • If target in (nums[mid], nums[hi]], search right; else search left.
Java
class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) return mid;
            if (nums[lo] <= nums[mid]) { // left sorted
                if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else { // right sorted
                if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }
}
  • Time Complexity: O(log N)
  • Space Complexity: O(1)