学步园

Search in Rotated Sorted Array

我的思路：

1、在一个没有重复数字，已经排序好的，旋转过的数组中找到一个数，返回数组中的下标，如果没有返回-1。

2、找到旋转的轴，然后进行两段二分查找。

3、关键是找到mid这个点。我使用的是两个指针从后面往前遍历查找。

class Solution {
public:
    int search(int A[], int n, int target) {
        if (n < 0)
            return -1;
        int begin = 0, end = n -1;
        while (A[begin] > A[end]) {
            begin++;
            end--;
        }
        int mid = begin == end ? (A[begin - 1] < A[begin] ? begin : begin - 1) : (A[end] > A[end + 1] ? end : begin - 1);
    
        int ans = binary_find(A, 0, mid, target);
        if (ans != -1)
            return ans;
        else
            return binary_find(A, mid + 1, n - 1, target);
    }
private:
    int binary_find(int *A, int low, int high, int target) {
        if (high < low)
            return -1;
        int mid = (low + high) / 2;
        while (low <= high) {
            if (A[mid] == target)
                return mid;
            else if (target > A[mid])
                low = mid + 1;
            else
                high = mid - 1;
            mid = (high + low) / 2;
        }
        return -1;
    }
};

别人思路：

1、别人都差不多，新的思路，见下一题。