在转动过的有序数组中寻找目标值（二分）

题意

求一个转动过的有序数组中, 找到值的索引

思路分析

转动的分界点性质

因为数组转动过,所以转动的位置一定是左侧大于右侧,而剩余的部分依然保持单调有序

分治

因为这样的分界点至多有一个考虑这个分界点的位置, [l...m][m+1...r]

如果分界点在左半数组,那么右半数组完全有序

如果分界点在右半数组,那么左半数组完全有序

如果分界点在中心,那么左半右半数组都有序

换句话说,总有一侧数组是完全有序

找值

又注意到原数组单调递增

因此可以对于完全有序的数组,直接判断是否在范围内

不在范围内则不需要搜索,在范围内搜索当前数组,另一半数组则不需要搜索

综上,通过每次把数组对半分开,对有序部分进行范围判断,进行搜索或继续分治,直到找到为止.

题目样例

以题目样例一为例[1],0,(样例二明显输入都是错的

题解

所以整合上面的内容

class Solution {
public:
    /**
     * 
     * @param A int整型一维数组 
     * @param n int A数组长度
     * @param target int整型 
     * @return int整型
     */
    int search(int* A, int n, int target) {
        if(n == 0)return -1;
        int l = 0;
        int r = n-1;
        while(l <= r){
            int m = (l+r)/2; // 分治数组
            // [l...m][m+1..r]
            // 左侧有序
            if(A[l] <= A[m]){
                // 在左侧之间
                if(A[l] <= target && target <= A[m]){
                    int idx = lower_bound(A+l,A+m+1,target) - A;
                    return A[idx] == target ? idx: -1;
                }else{ // 在右侧
                    l = m+1;
                }
            }else{ // 右侧有序
                // 在右侧之间
                if(A[m+1] <= target && target <= A[r]){
                    int idx = lower_bound(A+m+1,A+r+1,target) - A;
                    return A[idx] == target ? idx: -1;
                }else{ // 在左侧
                    r = m;
                }
            }
        }
        return -1;
    }
};

复杂度分析

空间复杂度: 只用了常数个额外变量,所以空间复杂度为$O(1)O(1)$

时间复杂度: 每次让范围减半,最后进行一次二分搜值,所以时间复杂度为$O(log(n))O(log(n))$