题解 | #在旋转过的有序数组中寻找目标值#

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

题意分析：

在数组中查找target

题解一（直接遍历）：

直接遍历判断有没有target，有返回下标，没有返回-1；

代码实现如下

int search(vector<int> &nums, int target) {
    for (int i = 0; i < nums.size(); i++) {
        if (target == nums[i]) {
            return i;
        }
    }
    return -1;
}

时间复杂度： $O(n)$ ，n为数组长度.

空间复杂度： $O(1)$

题解二（二分查找）：

如果给定的数组是排序好的数组，那么直接用二分法查找即可。但所给的数组是排序数组旋转后的数组，由两部分有序的部分组成。是否可以用二分法？

既然所给的数组修改了一下，那么也对二分查找进行修改一下。

假设从left到k，k+1到right为两个有序部分，mid一定位于（left，k）（k+1，right）两个区间之内，那么（left，mid）和（mid，right）这两个区间必定有一个是有序的，我们可以通过比较numsp[left]和nums[mid],nums[right]之间的大小关系得到那个区间有序

假设（left，mid）这段区间有序，

如果有target>mid,那么区间（left，mid）就应该被舍弃，下一步搜索区间为(mid+1,right)
如果targe<mid，并且nums[left]>target，区间（left，mid）也应该被舍弃,下一步搜索区间为(mid+1,right)
如果target<mid，并且nums[left]<target，下一步搜索区间应该为（left，mid），区间（mid+1，right）应该被舍弃。
如果相等，直接返回

（mid+1，right）有序的话，过程同上。
旋转后的数组，数字之间的走势如下图中的红线
图片说明
假设这段区间的mid在下图中这个位置，我们容易判断出left到mid是有序的，如果目标值小于mid，我们就在left到mid这段区间查找，这部分就变为有序数组的查找了

如果目标值大于mid，我们在mid-right这部分查找，这部分区间的走势和原来区间的走势是一样的，如图中黑色部分。
图片说明

如果mid掉落在非有序的那部分，分析过程一样。
代码实现如下：

int search(vector<int> &nums, int target) {
    int left = 0,right = nums.size()-1;
    int mid;
    while(left<=right){
        mid = left+(right-left)/2;
        if(nums[mid]==target){
            return mid;
        }
        if(nums[mid]>=nums[left]){
            //如果从left到mid有序
            if(target>nums[mid]||(target<nums[mid]&&target<nums[left])){
                left = mid+1;
            }
            else{
                right = mid;
            }
        }
        else if(nums[mid]<nums[right]){
            //如果从mid到right有序，更新区间
            if(target<nums[mid]||(target>nums[mid]&&target>nums[right])){
                right = mid;
            }
            else{
                left = mid+1;
            }
        }
    }
    return -1;
}

时间复杂度： $O(lg \ n)$ ，我们每次n为数组长度.

空间复杂度： $O(1)$