Home > Data Structures and Algorithms Questions >Search an element in a rotated sorted array .
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;
}