Search in Rotated Sorted Array LeetCode Solution

/ Leetcode Solution / Array, Binary Search, Bloomberg, C++ Solution, Facebook, Java Solution, JavaScript Solution, LeetCode Solution, Linkedin, Medium, Microsoft, Python Solution, Uber

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

List of all LeetCode Problem Solution
Search in Rotated Sorted Array 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

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;
    }       
};
Code language: C++ (cpp)

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;        
    }
}
Code language: Java (java)

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;  
};
Code language: JavaScript (javascript)

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
Code language: Python (python)

Related Posts