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.

ps：这题和剑指offter的题目类似。一次AC

思路，由于没有重复数字，

1.我们先找出最大值在哪个位置。

2.然后拿target和A[0]做比较，若target>A[0],则在0~max_loc之间来二分查找数组；若target<A[0]，则在max_loc+1~n-1来查找数组。

代码：

class Solution {

public:

    int binarySearch(int start,int end,int A[],int target){

        int l=start;int r=end;int mid=;

        while(l<=r){

            mid=(l+r)/;

            if(A[mid]>target) r=mid-;

            else if(A[mid]<target) l=mid+;

            else return mid;

        }

        return -;

    }

    int findMaxValueLoction(int A[],int n){

        if(A[n-]>A[]) return n-;

        int l=;int r=n-;int mid=;

        while(l<=r){

            mid=(l+r)/;

            if(mid==) return mid;

            else if(mid!=&&A[mid]>A[]&&A[mid]>A[mid-]&&A[mid]<A[mid+]){

                l=mid+;

            }

            else if(mid!=&&A[mid]<A[]&&A[mid]>A[mid-]&&A[mid]<A[mid+]){

                r=mid-;

            }

            else if(mid!=&&A[mid]>A[mid-]&&A[mid]>A[mid+]){

                return mid;

            }else{

                return mid-;

            }

        }

        return -;

    }

    int search(int A[], int n, int target) {

        if(A==NULL||n==) return -;

        int max_loc=findMaxValueLoction(A,n);

        if(target>A[])

            return binarySearch(,max_loc,A,target);

        else if(target<A[])

            return binarySearch(max_loc+,n-,A,target);

        else

            return ;

    }

};

巴特西

Search in Rotated Sorted Array（二分查找）

最新文章

热门文章