Search in Rotated Sorted Array

Medium Problem 46 of 151 Java and Python

Problem

An ascending array of distinct integers has been rotated at an unknown pivot (for example [0, 1, 2, 4, 5, 6, 7] → [4, 5, 6, 7, 0, 1, 2]).

Given the rotated array nums and target, return the index of target, or -1 if it is not there, in O(log n) time.

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

Constraints

1 ≤ nums.length ≤ 5000
All values are unique.

Explanation

Split at mid: at least one of the two halves is in normal sorted order. You can tell which by comparing nums[lo] with nums[mid].

For the sorted half, checking whether the target falls inside it is a simple range check. If it does, search there; otherwise search the other half.

Approach 1 · Naive

Linear scan

Time O(n)
Space O(1)

Check every index.

Return the index where nums[i] == target, else -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;
    }
}

Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        return nums.index(target) if target in nums else -1

Approach 2 · Optimal

Binary search, pick the sorted half

Time O(log n)
Space O(1)

Each step, find which half is sorted and whether the target lies within it.

While lo <= hi: if nums[mid] == target, return mid.
If nums[lo] <= nums[mid] (left half sorted): go left if nums[lo] <= target < nums[mid], else go right.
Otherwise (right half sorted): go right if nums[mid] < target <= nums[hi], else go left.

Java

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            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;
    }
}

Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[lo] <= nums[mid]:
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return -1

Complexity compared

Approach	Time	Space
Naive Linear scan	O(n)	O(1)
Optimal Binary search, pick the sorted half	O(log n)	O(1)

Key takeaways

Use <= in nums[lo] <= nums[mid]: when lo == mid the left "half" is one element and counts as sorted.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem