Course4all

Search in Rotated Sorted Array

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Binary Search.

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(logN)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
  1. Find pivot (min element): nums[4] = 0. Pivot index is 4.
  2. Target 0 >= nums[4] and 0 <= nums[6] (2). Target is in right half [4..6].
  3. 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

StepLRMidnums[Mid]Sorted?Target In?Decision
10637Left [0..3]No (0 < 4 or 0 > 7)L = 4
24651Right [5..6]No (0 < 1 or 0 > 2)R = 4
34440Found!-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;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionFind Minimum in Rotated Sorted Array
Next Question →Search a 2D Matrix