Start practising

Search in Rotated Sorted Array

Medium Binary Search Rotated Array Original on LeetCode

Search in Rotated Sorted Array is a medium binary search problem solved with the rotated array pattern. The best approach, optimal (find the sorted half), runs in O(log n) time and O(1) space. Below are 2 approaches in Java, from linear scan up.

Problem

A sorted array of distinct integers was rotated at an unknown pivot. Given a target, return its index or -1, in O(log n) time.

Examples

Example 1

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

Example 2

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

Constraints

  • 1 <= nums.length <= 5000, distinct values.
  • O(log n).

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Linear scanO(n)O(1)
Optimal (find the sorted half)O(log n)O(1)

1Linear scan

TimeO(n)
SpaceO(1)

Check every element.

  1. Return the index of target or -1.
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;
    }
}

2Optimal (find the sorted half)

TimeO(log n)
SpaceO(1)

If nums[lo] <= nums[mid], the left half is sorted: search it when target is in [nums[lo], nums[mid]), otherwise go right. If not, the right half is sorted: search it when target is in (nums[mid], nums[hi]], otherwise go left.

  1. If nums[mid] == target, return mid.
  2. Left sorted: nums[lo] <= target < nums[mid] ? hi = mid - 1 : lo = mid + 1.
  3. Right sorted: nums[mid] < target <= nums[hi] ? lo = mid + 1 : hi = mid - 1.
Java
class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (nums[mid] == target) return mid;
            if (nums[lo] <= nums[mid]) {
                if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }
}

Edge cases to test

  • Not rotated
  • Target at the rotation point

Hints

Hint 1

At any mid, at least one of the halves [lo, mid] and [mid, hi] is sorted. Check whether the target falls in that sorted half.

FAQ

What is the best time complexity for Search in Rotated Sorted Array?

Optimal (find the sorted half) runs in O(log n) time and O(1) extra space.

Which pattern does Search in Rotated Sorted Array use?

It is a binary search problem that uses the rotated array pattern. Other problems with the same pattern: Find How Many Times Array is Rotated, Find Minimum in Rotated Sorted Array, Find Minimum in Rotated Sorted Array II.

Is there a brute force solution for Search in Rotated Sorted Array?

Yes. Linear scan takes O(n) time and O(1) space. Check every element.

Which edge cases should I test for Search in Rotated Sorted Array?

Not rotated; Target at the rotation point.