对旋转数组进行均等划分后,总有一边是有序的,如:

  1. 10 11 12 13 14 15 1 2 3
  2. 10 11 15 1 2 3 4 5 6 7 8

我们定位到有序的一边后,对比target与有序子数组的左右边界,就可以作出搜索左侧还是右侧的决策。

代码如下:

第16行必须是<=,不能是<,举例——从[3,1]中查找1

//
// Created by jt on 2020/9/3.
//
class Solution {
public:
    /**
     *
     * @param A int整型一维数组
     * @param n int A数组长度
     * @param target int整型
     * @return int整型
     */
    int search(int* A, int n, int target) {
        // write code here
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == target) return mid;
            if (A[mid] >= A[left]) {
                // 左侧有序(含A[mid])
                if (A[mid] > target && A[left] <= target)
                    right = mid - 1;
                else
                    left = mid + 1;
            } else {
                // 右侧有序(含A[mid])
                if (A[mid] < target && A[right] >= target)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
        return -1;
    }
};