搜索旋转排序数组

题目：

整数数组 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

思路:

题目要求时间复杂度是 O(logn)，想到用二分法解题。二分法要求整个数组是有序的，但题目中给的数组是经过旋转的，是无序数组。

经过观察发现：

• 经过旋转的数组，从数组中任意一个位置分隔开，所形成的数组中必定有一个是有序的，另一个可能是有序，也可能是无序的；
• 同时对上一步中的无序数组再次分割，得到的两个数组，也必定一个是有序，另一个可能是有序，也可能是无序；

所以，可以使用二分法解题。

• 首先，定义两个指针 left = 0 、 right = nums.length - 1。
• 使用 while 循环，当 left > right 的时候，跳出循环。
• while 循环体中，每次取 mid = parseInt((left + right) / 2) 中间指针。
  • 当 target === nums[mid] 的时候，说明找到目标值的下标，循环结束，返回下标。
  • 当 nums[mid] > nums[left] 的时候，说明左侧数组是有序排列的，此时：
    • 如果 nums[left] <= target < nums[mid]，说明 target 在左侧数组中，只需要把 right 指针改为 mid -1 ，然后继续循环。
    • 否则，说明 target 在右侧数组中，此时右侧数组可能是有序的也可能是无序的，所以把 left 指针的位置改为 mid + 1 的位置，继续循环
  • 当 nums[mid] < nums[left] 的时候，说明右侧数组是有序排列的，此时：
    • 如果 nums[mid] < target <= nums[rught] ，说明 target 在右侧数组中，把 left 指针改为 mid -1 后，继续循环。
    • 否则 ,说明 target 在左侧数组中（此时右侧数组可能是有序的也可能是无序的）, 把 right 指针位置改为 mid - 1 ，继续循环。
• 最终，如果都没找到，返回 -1

代码：

const search = (nums, target) => {
        if (nums.length <= 0) return -1;
        let left = 0,
            right = nums.length - 1;
 
        while (left <= right) {
            let mid = parseInt((left + right) / 2);
 
            if (nums[mid] === target) return mid;
            if (nums[left] > nums[mid]) { // 说明 mid 右侧是升序排列
                if (nums[mid] < target && target <= nums[right]) { // 如果 target 在 mid 和 right 之间，就改变 left 位置，继续循环
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else { // 说明左侧是升序列表
                if (nums[left] <= target && target < nums[mid]) { // 如果 target 在 left 和 mid 之间，就改变 right 位置，继续循环
                    right = mid - 1;
                } else {
                    left = mid + 1
                }
            }
        }
        return -1
    }