在转动过的有序数组中寻找目标值

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

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;
    }
};