Algorithm Day67 - Search in Rotated Sorted Array

Posted on In , Views:

🧩 Problem Description

There is an integer array nums sorted in ascending order (with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length).

Given the array nums after the rotation 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.

💬 Examples

Example 1

1
2
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2

1
2
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3

1
2
Input: nums = [1], target = 0
Output: -1

💡 Intuition

Since the array is rotated sorted, one half is always sorted:

  • If the target lies within the sorted half, continue searching in that half.
  • Otherwise, search in the other half.

This is a modified binary search. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;

            // Left half is sorted
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { // Right half is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

⏱ Complexity Analysis

  • Time: O(log n) — modified binary search.
  • Space: O(1) — no extra space.

✍️ Summary

  • Use binary search with conditions to detect the sorted half.
  • Move search boundaries accordingly.

Related problems

  • lc-34 — Find First and Last Position of Element
  • lc-81 — Search in Rotated Sorted Array II