Search in Rotated Sorted Array

MEDIUM

Description

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

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

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

Example 3:

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

Constraints:

1 <= nums.length <= 5000
-10⁴ <= nums[i] <= 10⁴
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-10⁴ <= target <= 10⁴

Approaches

Checkout 2 different approaches to solve Search in Rotated Sorted Array. Click on different approaches to view the approach and algorithm in detail.

Linear Search (Brute Force)

The most straightforward approach is to perform a linear scan of the array. We can iterate through each element from the beginning to the end and check if it matches the target value. If a match is found, we return its index. If we traverse the entire array without finding the target, we return -1.

Algorithm

Initialize a loop counter i to 0.
Iterate through the nums array from i = 0 to nums.length - 1.
In each iteration, check if the current element nums[i] is equal to the target.
If they are equal, the target is found. Return the current index i.
If the loop completes without finding the target, it means the target is not in the array. Return -1.

This brute-force method ignores the special properties of the rotated sorted array and treats it like any other unsorted list. It's simple to implement but fails to meet the performance requirements for larger datasets.

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;
    }
}

Complexity Analysis

Time Complexity: O(n)Space Complexity: O(1)

Pros and Cons

Pros:

Very simple to understand and implement.
Works correctly for any array, regardless of its properties.

Cons:

Inefficient for large arrays as it may require scanning the entire array.
Does not meet the O(log n) time complexity requirement specified in the problem description.

Code Solutions

Checking out 5 solutions in different languages for Search in Rotated Sorted Array. Click on different languages to view the code.

public class Solution {
    public int Search(int[] nums, int target) {
        int n = nums.Length;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target <= nums[mid]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
        }
        return nums[left] == target ? left : -1;
    }
}

Video Solution

Watch the video walkthrough for Search in Rotated Sorted Array

Algorithms:

Binary Search

Data Structures:

Array

Companies:

Accolite |Adobe |Amazon |Apple |