[33] 搜索旋转排序数组

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

( 例如，数组 [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

这道题，解题的关键在于找到旋转的起始索引位置，之后的解题方式就是普通的二分查找有序数组了。

解法一

由于旋转前数组有序，因此只要我们在遍历数组时，找到前一个数比后一个数大的情况，即找到了旋转起始点。

  let start = 0;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < nums[i - 1]) {
      start = i;
      break;
    }
  }

该起始点为中心，将数组分为了两个升序数组，那么我们只需要判断target在哪一侧数组，即可确定二分搜索的上下界，从而完成解题。

  if (target === nums[0]) {
    // 如果target恰好等于第一个，则直接返回0索引
    return 0;
  } else if (target > nums[0] && start !== 0) {
    // 当target大于最左侧元素，此时target在左半边序列中查询。
    // 注意，当start=0时，此时没有左半边序列，只能从右半边序列中查询
    left = 0;
    right = start - 1;
  } else {
    // target在右半边序列中查询
    left = start;
    right = nums.length - 1;
  }

确定了上下界，二分搜索求结果的方法就非常常规了，不理解的可以去看看专题中二分搜索的解法介绍。

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;

至此，题目就AC通过了。

但是，由于题目要求时间复杂度为O(lgn)，因此，查找旋转起点的方式也必须使用二分法。

  let left = 0,
    right = nums.length,
    start = 0;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] > nums[mid + 1]) {
      // 说明此时找到了旋转位置，位置为 mid + 1
      start = mid + 1;
      break;
    } else {
      // 通过二分缩小查询范围
      if (nums[mid] > nums[left]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
  }

时间总复杂度为O(2lgn),符合要求。

function search(nums: number[], target: number): number {
  let left = 0,
    right = nums.length,
    start = 0;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] > nums[mid + 1]) {
      // 说明此时找到了旋转位置，位置为 mid + 1
      start = mid + 1;
      break;
    } else {
      // 通过二分缩小查询范围
      if (nums[mid] > nums[left]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
  }

  if (target === nums[0]) {
    // 如果target恰好等于第一个，则直接返回0索引
    return 0;
  } else if (target > nums[0] && start !== 0) {
    // 当target大于最左侧元素，此时target在左半边序列中查询。
    // 注意，当start=0时，此时没有左半边序列，只能从右半边序列中查询
    left = 0;
    right = start - 1;
  } else {
    // target在右半边序列中查询
    left = start;
    right = nums.length - 1;
  }

  // 正常二分查找
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}

解法二

我们也可以换一种思路来解题。我们注意到，由于有序数组只旋转一次，那么对于任意一点，一定有左侧或者右侧符合单调递增，另一侧不符合。

可以利用这一特性在一次遍历中二分缩小查找比对范围。

var search = function(nums, target) {
  if (!nums || nums.length === 0) return -1;

  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (target === nums[mid]) {
      return mid;
    } else if (nums[mid] >= nums[left]) {
      // 说明[left, mid]之间是有序的
      if (target < nums[mid] && target >= nums[left]) {
        // 因为[left, mid]有序，若target在左侧范围内，则一定会大于nums[left]小于nums[mid]
        right = mid - 1;
      } else {
        // 反之一定不在该本次二分的有序范围内，递归右侧
        left = mid + 1;
      }
    } else if (nums[mid] <= nums[right]) {
      // 说明[mid, right]之间是有序的
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  return -1;
};