首页 > 代码库 > Search in Rotated Sorted Array

Search in Rotated Sorted Array

Suppose a sorted array 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).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

 

Hide Tags
 Array Binary Search
 
class Solution {public:    int findPos(int a[],int left,int right){        if(left>right)            return -1;        int mid=left+(right-left)/2;        if(a[left]<=a[mid]){            int pos=findPos(a,mid+1,right);            if(pos==-1)                return left;            else                return a[left]<=a[pos] ? left : pos;        }else{            int pos=findPos(a,left,mid-1);            if(pos==-1)                return mid;            else                return a[pos]<a[mid] ? pos : mid;        }    }        int bsearch(int a[],int left,int right,int key){        if(left>right)            return -1;        int mid=left+(right-left)/2;        if(a[mid]==key)            return mid;        else if(a[mid]<key)            return bsearch(a,mid+1,right,key);        else             return bsearch(a,left,mid-1,key);    }        int search(int A[], int n, int target) {        int pos=findPos(A,0,n-1);        int index=bsearch(A,0,pos-1,target);        if(index!=-1)            return index;        else            return bsearch(A,pos,n-1,target);    }};

 

Search in Rotated Sorted Array