Leetcode--Search in Rotated Sorted Array（旋轉數組的查找）

Problem Description：

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.

分析：

有序數組的查找直接使用二分查找很方便，所以旋轉之後的數組要利用二分搜索的原理需要判斷哪一部分仍然是有序的，然後確定在哪一部分繼續搜索。具體判斷方法如下：

（1）如果target==A[mid]，那麼mid就是我們要的結果，直接返回；

（2）如果A[begin]<=A[mid]，那麼說明從begin到mid一定是有序的，同樣只需要判斷target是否在這個范圍內，如果是則把右邊緣移到mid-1，否則就target在另一半，即把左邊緣移到mid+1。

（3）如果A[begin]>A[mid]，那麼說明從mid到last一定是有序的（沒有受到rotate的影響），那麼我們只需要判斷target是不是在mid到last之間，如果是則把左邊緣移到mid+1，否則就target在另一半，即把右邊緣移到mid-1。

代碼如下：

class Solution {
public:

    int binarysearch(int a[],int begin,int last,int target)
    {
        
        if(begin>last)
            return -1;
        int mid=(begin+last)/2;
        if(a[mid]==target)
            return mid;
        if(a[begin]<=a[mid]) //這裡一定要加上“=”，例子：3,1中尋找3
        {
            if(target>=a[begin]&&targeta[mid]&&target<=a[last])
                return binarysearch(a,mid+1,last,target);
            else
                return binarysearch(a,begin,mid-1,target);
        }
    }

    int search(int A[], int n, int target) {
        int flag=-1;
        if(n==0)
            return -1;

        flag=binarysearch(A,0,n-1,target);
        return flag;
    }
};

下面是非遞歸的代碼：

class Solution {
public:

    int search(int A[], int n, int target) {
        int begin = 0, last = n-1;
        while (begin <= last)
        {
            int mid =(begin + last) / 2;
            if (A[mid] == target)
                return mid;
            if (A[begin] <= A[mid]) 
            {
                if (A[begin] <= target && target < A[mid])
                    last = mid-1;
                else
                    begin = mid + 1;
            } 
            else
            {
                if (A[mid] < target && target <= A[last])
                    begin = mid + 1;
                else
                    last = mid-1;
            }
        }
        return -1;
        }
};