【每日一题】33 搜索旋转排序数组

题目地址@LeetCode-search-in-rotated-sorted-array (opens new window)

题意：

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回-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

解（来自题解）

偷瞄的题解的思路。。

该题解来自于LeetCode@lucifer (opens new window)

由算法时间复杂度必须为O(log n)可知查找算法需为折半查找。题意是升序数组在某一个点上发生了旋转，那么必有一个 分界点 ，它左右两侧的数都是有序的，但是连在一起是无序的。

查找时先将 中间数nums[mid] 与第一个数进行比较确定中间数nums[mid] 的位置是在左边的有序部分还是右边的有序部分，之后再用target与边界进行比较以确定target的位置：

1.nums[mid] > nums[start]：

此时可以确定nums[mid]在左边有序部分，接下来比较边界确定target位置，

• nums[start] <= target && target <= nums[mid]：此时将右边界移至mid - 1;
• 与上面相反的话说明target在右侧有序部分，将左边界移至mid + 1。

2.nums[mid] > nums[start]：

此时nums[mid]在右边有序部分，

• nums[mid] <= target && target <= nums[end]：将左边界移至mid + 1;
• 与上面相反则将右边界移至mid - 1。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
  let start = 0;
  let end = nums.length - 1;

  while (start <= end) {
    const mid = start + ((end - start) >> 1);// 取中间点 移位
    if (nums[mid] === target) return mid;

    if (nums[mid] >= nums[start]) {
      // 左边有序部分
      if (nums[start] <= target && target <= nums[mid]) {
        end = mid - 1;
      } else {
        start = mid + 1;
      }
    } else {
      // 右边有序部分
      if (nums[mid] <= target && target <= nums[end]) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    }
  }
  return -1;
};