Blogs Hub

by Sumit Chourasia | Oct 24, 2020 | Category :coding | Tags : algorithm array data-structure leetcode medium

Search in Rotated Sorted Array - Array - Medium - LeetCode

Search in Rotated Sorted Array - Array - Medium - LeetCode

You are given an integer array nums sorted in ascending order, and an integer target.

Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

If target is found in the array return its index, otherwise, return -1.

 

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^4 <= nums[i] <= 10^4
All values of nums are unique.
nums is guranteed to be rotated at some pivot.
-10^4 <= target <= 10^4

public class Solution {
    public int Search(int[] nums, int target) {
        int low = 0;
        int high = nums.Length-1;
        int len = nums.Length;
        while(low<high){
            int mid = low+(high-low)/2;
            if(nums[mid]>nums[high]){
                low=mid+1;
            }
            else{
                high=mid;
            }
        }
        
        int rotation = low;
        
        low=0;
        high = nums.Length-1;
        while(low<=high){
            int mid = low+(high-low)/2;
            int actualMid = (mid + rotation)%len;
            if(nums[actualMid]==target){
                return actualMid;
            }
            else if(nums[actualMid]<target){
                low=mid+1;
            }
            else{
                high=mid-1;
            }                    
        }
        
        return -1;
    }
        
}

Time Complexity: O(logn)

Space Complexity: O(1)

Contributed By: Sumit Chourasia
Circular Array Loop - Array - Medium - LeetCode
Contributed By: Sumit Chourasia
Teemo Attacking - Array - Medium - LeetCode
Contributed By: Sumit Chourasia
Array Nesting - Array - Medium - LeetCode