【刷题笔记】搜索旋转排序数组

题目：

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：

输入：nums = [1], target = 0
输出：-1
 

提示：

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-in-rotated-sorted-array

        首先想到的是利用二分法去寻找。但是二分法有一个非常致命的要求--就是选取的区域必须是有序的。那么上面这个旋转数组该如何去寻找呢？-->还是使用二分法。

解法：

        我们可以发现，利用二分法的找中，将一个旋转数组一分为2之后，存在一部分一定有序。比如：[5 6 7 8 0 1 2 3 4]   --> [5 6 7 8 0]  [1 2 3 4] 然后没有顺序的继续分 --> [5 6 7] [8 0] -> [8] [0]...

可以发现，每次一分都会存在有顺序的，直到最后分成两个一个数字的停止。

        那么找到有顺序的，是不是就可以使用二分法寻找了呢？答案是的。比如上述例子中找 3，那么第一次分成两半后，先判断哪边是有序的，如果有序且满足找的这个数在此区域内，那么，就可以将区域压缩到有序里面进行二分查找即可。如果有哪个条件不满足（没有序或者不在其区间内），那么就重复第一次的步骤，在无序里去划分。

        所以，我们可以首先区分0下标和mid下标这段区域是否有序，有序就进入这个里面。判断满不满足目标值在此内，不再此内就定位到无序区。否则就是第二段区域有序，重复上述步骤，直到结束。找到了就返回其下标。循环结束就说明没找到，返回-1。

        当然特殊情况就是传入空数组或者只有一个数，单独进行判断即可。

代码如下：

int search(int* nums, int numsSize, int target){
    if (numsSize == 0)
        return -1;
    if (nums[0] == target)
        return 0;
    int begin = 0;
    int end = numsSize - 1;
    while(begin <= end)
    {
        int mid = begin + (end - begin) / 2;
        if (nums[mid] == target)
            return mid;
        if (nums[0] <= nums[mid])
        {
            if (target < nums[mid] && target >= nums[0])
                end = mid - 1;
            else
                begin = mid + 1;
        }
        else
        {
            if (target <= nums[numsSize - 1] && target > nums[mid])
                begin = mid + 1;
            else
                end = mid - 1;
        }
    }
    return -1;
}