Search In Rotated Sorted Array Problem Solution

Search In Rotated Sorted Array Problem: 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 :

Input: nums = [4,5,6,7,0,1,2], target = 0

Output: 4

Search In Rotated Sorted Array Problem Solution

Problem Solution In Python

class Solution:
    def search(self, nums, target):    
        def search(nums, l, r):
            m = (l + r) // 2
            if nums[m] == target:
                return m
            if l == r:
                return -1
            if nums[l] < nums[m]:
                if target >= nums[l] and target < nums[m]:
                    return search(nums, l, m - 1)
                else:
                    return search(nums, m + 1, r)
            elif r - m == 1:
                if nums[r] == target:
                    return r
                else:
                    return search(nums, l, m)
            elif nums[m + 1] < nums[r]:
                if target >= nums[m + 1] and target <= nums[r]:
                    return search(nums, m + 1, r)
                else:
                    return search(nums, l, m - 1)
            return -1

        return -1 if not nums else search(nums, 0, len(nums) - 1)

Problem Solution In Java

class Solution {
    public int search(int[] nums, int target) {
        
        if(nums.length == 1){
            return nums[0] == target ? 0 : -1;    
        }
        int i=0;
        int j = nums.length-1;
        while(i<j){
            if(nums[i] == target){
                return i;
            }
            else if(nums[j] == target){
                return j;
            }
            else if(target > nums[i]){
                i++;
            }
            else{
                j--;
            }
        }
        return -1;
    }
}

Problem Solution In C++

class Solution {
public:
    int b_Search(vector<int>& nums, int target, int low, int high) {
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target) high = mid - 1;
            else low = mid + 1;
        }
        return -1;
    }
    
    int search(vector<int>& nums, int target) {
        int i = 0;
        for(; i < nums.size() - 1; i++) {
            if(nums[i] > nums[i + 1]) break;
        }
        int ans = b_Search(nums, target, 0, i);
        if(ans != -1 || i == nums.size() - 1) return ans; 
        ans = b_Search(nums, target, i+1, nums.size() - 1);
        return ans;
    }
};

Problem Solution In C

int search(int* nums, int numsSize, int target){

    int i = 0;
for(i = 0;i<numsSize;i++)
{
    if((nums[i] == target) ) 
        return i;
    if((nums[numsSize - i-1] == target ))
        return (numsSize-i-1);
}

return -1;
}