Search in Rotated Sorted Array LeetCode Solution

Last updated on January 29th, 2025 at 02:27 am

Here, we see a Search in Rotated Sorted Array LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Binary Search

Companies

Bloomberg, Facebook, Linkedin, Microsoft, Uber

Level of Question

Medium

Search in Rotated Sorted Array LeetCode Solution

Search in Rotated Sorted Array LeetCode Solution

1. Problem Statement

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.

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].

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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Modified Binary Search. This pattern is a variation of the standard binary search algorithm, where the search space is adjusted based on specific conditions. In this case, the array is rotated, and the algorithm determines which part of the array to search based on the rotation and the target value.

3. Code Implementation in Different Languages

3.1 Search in Rotated Sorted Array C++

class Solution {
public:
    int search(vector<int>& nums, int target) {
int beg=0,end=nums.size()-1,mid;
        while(beg<=end)
        {
            mid=(beg+end)/2;
            if(nums[mid]==target)
                return mid;
            if(nums[beg]<=nums[mid])
            {
                if(target<=nums[mid] && target>=nums[beg])
                    end=mid-1;
                else
                    beg=mid+1;
            }
            else
            {
                if(target>=nums[mid] && target<=nums[end])
                   beg=mid+1;
                else
                    end=mid-1;
            }
        }
        return -1;
    }       
};

3.2 Search in Rotated Sorted Array Java

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

3.3 Search in Rotated Sorted Array JavaScript

var search = function(nums, target) {
    let start = 0, end = nums.length - 1;
    while(start<end){
        let mid = Math.floor((start+end)/2);
        if(nums[mid]===target) return mid;

        if(nums[mid]>nums[start]){
            if(target>=nums[start] && target<nums[mid]) end = mid-1;
            else start = mid+1;
        }
        else if(nums[mid]<nums[end]){
            if(target>nums[mid] && target<=nums[end]) start = mid+1;
            else end = mid-1;      
        }
        else break;
    }
    return nums[end]===target?end:-1;  
};

3.4 Search in Rotated Sorted Array Python

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

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(log n)O(1)
JavaO(log n)O(1)
JavaScriptO(log n)O(1)
PythonO(log n)O(1)
Scroll to Top