Coding Ninjas Logo

Home > Data Structures and Algorithms Questions >Search an element in a rotated sorted array .

Search an element in a rotated sorted array .

Answer:

Here's a code snippet search an element in a rotated sorted array in O(logn) time.

                    public int search(int[] nums, int target) {

if(nums.length==0) return -1;
int pivot = 0;
int left = 0;
int right = nums.length-1;
while(left int mid = left+(right-left)/2;
if(nums[mid]>nums[right]){
left = mid+1;
}
else{
right = mid;
} } pivot = left; if(nums[pivot]==target) return pivot; int[] leftnums = Arrays.copyOfRange(nums,0,pivot); int[] rightnums = Arrays.copyOfRange(nums,pivot+1,nums.length); int ans = -1; if(leftnums.length>0 && target>=leftnums[0]){ ans = BinarySearch(leftnums,target); } else{ ans = BinarySearch(rightnums,target); if(ans!=-1) return ans+pivot+1; } return ans; }

public int BinarySearch(int[] nums,int target){ int left = 0; int right = nums.length-1; while(left<=right){ int mid = left+(right-left)/2; if(nums[mid]==target){ return mid; } else if(nums[mid]>target){ right = mid-1; } else{ left = mid+1; } } return -1; }



Similar Questions