Search in Rotated Sorted Array

Master this topic with zero to advance depth.

Search in Rotated Sorted Array

Given the array nums after a possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums. All values in nums are unique. You must write an algorithm that runs in $O(\\log N)$ time.

Medium

Examples

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

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

Approach 1

Level I: Brute Force

Intuition

The simplest way is to iterate through the entire array and check if any element equals the target.

⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

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

i=0: 4 != 0
i=1: 5 != 0
i=2: 6 != 0
i=3: 7 != 0
i=4: 0 == 0. Return 4.

java

class Solution {
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) return i;
        }
        return -1;
    }
}

Approach 2

Level II: Find Pivot + Two Binary Searches

Intuition

First, find the index of the minimum element (the pivot). This splits the array into two sorted halves. Perform a standard binary search on the appropriate half.

⏱ $O(\\log N)$💾 $O(1)$

Detailed Dry Run

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

Find pivot (min element): nums[4] = 0. Pivot index is 4.
Target 0 >= nums[4] and 0 <= nums[6] (2). Target is in right half [4..6].
Binary search on [4..6] for 0. Found at index 4.

java

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[r]) l = mid + 1;
            else r = mid;
        }
        int pivot = l;
        l = 0; r = n - 1;
        if (target >= nums[pivot] && target <= nums[r]) l = pivot;
        else r = pivot - 1;
        
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return -1;
    }
}

Approach 3

Level III: Optimal (Single Pass Binary Search)

Intuition

In every step, at least one half of the current range must be sorted. We check which half is sorted and determine if the target lies within it. This avoids finding the pivot separately.

⏱ $O(\\log N)$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	nums[Mid]	Sorted?	Target In?	Decision
1	0	6	3	7	Left [0..3]	No (0 < 4 or 0 > 7)	L = 4
2	4	6	5	1	Right [5..6]	No (0 < 1 or 0 > 2)	R = 4
3	4	4	4	0	Found!	-	Return 4

java

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) return mid;
            if (nums[l] <= nums[mid]) { // Left half is sorted
                if (target >= nums[l] && target < nums[mid]) r = mid - 1;
                else l = mid + 1;
            } else { // Right half is sorted
                if (target > nums[mid] && target <= nums[r]) l = mid + 1;
                else r = mid - 1;
            }
        }
        return -1;
    }
}

← Previous QuestionFind Minimum in Rotated Sorted Array

Next Question →Search a 2D Matrix

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.