Last updated on October 10th, 2024 at 02:03 am

Here, We see Search in Rotated Sorted Array LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

Search in Rotated Sorted Array LeetCode Solution

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

1. Search in Rotated Sorted Array Leetcode Solution 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;
    }       
};

2. Search in Rotated Sorted Array Leetcode Solution 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. Search in Rotated Sorted Array Leetcode Solution 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;  
};

4. Search in Rotated Sorted Array Leetcode Solution 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