首页 > 代码库 > 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.

 

C++代码实现:

#include<iostream>using namespace std;class Solution{public:    int search(int A[], int n, int target)    {        int left=0;        int right=n-1;        int mid;        while(left<=right)        {            mid=(left+right)/2;            if(A[mid]==target)                return mid;            else if(A[mid]<target&&A[mid]>A[right])                left=mid+1;            else if(A[mid]<target&&A[mid]<A[right])            {                if(target>A[right])                    right=mid-1;                else if(target<A[right])                    left=mid+1;                else                    return right;            }            else if(A[mid]>target&&A[mid]>A[right])            {                if(target>A[right])                    right=mid-1;                else if(target<A[right])                    left=mid+1;                else                    return right;            }            else if(A[mid]>target&&A[mid]<A[right])                right=mid-1;            else                return -1;        }        if(left>right)            return -1;        else            return mid;    }};int main(){    Solution s;    int A[10]= {2,3,4,5,6,7,8,9,10,1};    cout<<s.search(A,10,5)<<endl;}

 

Search in Rotated Sorted Array