一.题目描述
NC48在旋转过的有序数组中寻找目标值
题目链接:
https://www.nowcoder.com/practice/87c0e7abcbda41e7963660fa7d020995?tpId=196&&tqId=37078&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
给出一个转动过的有序数组，你事先不知道该数组转动了多少,在数组中搜索给出的目标值，如果能在数组中找到，返回它的索引，否则返回-1。假设数组中不存在重复项。
(例如:0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2).
二.算法
图片说明
首先，我们需要求出蓝色分界线的下标x。一旦求出分界点，我们就知道了两段有序数组的分界点，就可以对某一段进行二分查找。那么对于这两段区间，你会发现一个性质：
左边区间内所有的点都大于等于nums[0]，而右边区间内所有的点都小于nums[0]。所以，我们可以这样找到分界点x：

int n=nums.size();
int l=0,r=n-1;
while (l<r){
    int mid=l+r+1>>1;//加法的优先级高于位运算
    if (nums[mid]>=nums[0]) l=mid;
    else r=mid-1;
}

接下来的一个问题就是，我们如何确定应该在哪段升序区间进行二分查找？
令目标值target与nums[0]进行比较，若大于等于，说明是左边的，否则右边：

if (target >= nums[0]){
    l=0;//左边
} else {
    l=r+1;//右边
    r=n-1;
}

最后的问题就是在一个升序的序列中找一个目标值,下面是完整代码：

class Solution {
    public:
    int search(vector<int> nums, int target) {
        int n=nums.size();
        if (n==0) return -1;//要是一个空集 就直接返回-1
        int l=0, r=n-1;
        while (l<r){
            int mid = (l+r+1)>> 1;
            if (nums[mid] >= nums[0]) l=mid;
            else r = mid - 1;
        }
        //确定升序区间
        if (target >= nums[0]){
            l = 0;//左边
        } else {
            l=r+1;//右边
            r=n-1;
        }
        //在升序序列中寻找target
        while (l<r){
            int mid =(l+r)>> 1;
            if (nums[mid]>=target) r=mid;
            else l=mid+1;
        }
        if(nums[r]==target){//升序序列中有目标值
            return r;
        } else {
            return -1;
        }
    }
};

时间复杂度:o(logn)
空间复杂:o(1) 不需要开辟额外空间
优缺点:思路简单，但是写起来复杂

三.算法
有序数组中查找一般使用二分查找，但是这道题进行了转动。重点在于左右边界的确定，将整个旋转数组分为两部分一定有一部分有序，那么通过判断左边还是右边有序分为两种情况，然后再判断向左走还是向右走。
相比于有序的二分查找多一些判定条件：
(1)要么前半段有序，要么后半段有序。
(2)当前半段有序时：即循环数组中间值比循环数组最左边值大 则 nums[left]<nums[mid]当target比中间值小，比最左值（前半段最小值）大时，肯定在前面部分则right=mid-1 。如果不在前半段，可能在后半段，则right=mid+1。
(3)同理后半段也一样。

class Solution {
public:
    int search(vector<int> nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid=left+(right-left)/2; //防止相加产生溢出
            if(nums[mid]==target){
                return mid;
            } else if(nums[left]<=nums[mid]){ //如果左边有序
                //在左边有序范围内
                if(target>=nums[left]&&target<=nums[mid]){
                    right=mid-1;
                } else {
                    left=mid+1;//不在有序范围内，只能去右边找
                }
            } else{  //右边有序
                //在右边有序范围内
                if(target>=nums[mid]&&target<=nums[right]){
                    left=mid+1; //不在有序范围内，只能去左边找
                } else {
                     right=mid-1;
                }
            }
        }
        return -1;
    }
};

时间复杂度:o(logn)
空间复杂度:o(1)
优缺点：一个二分就可以解决，但是实现起来比较复杂