每天一道leetcode(Day 42)

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

解题思路

看到时间复杂度  O(log n)的要求第一时间想到的就是二分查找发，但是因为本题数组在某一点有旋转，因此只能保证局部有序。
因此我们在普通二分查找的基础上，添加一个有序数组的判断即可。

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let start = 0,
    end = nums.length - 1;
  while (start <= end) {
    const mid = start + Math.floor((end - start) / 2);
    if (nums[mid] === target) return mid;
    // 左边数组有序
    nums[mid] >= nums[start]
      ? target >= nums[start] && target <= nums[mid]
        ? (end = mid - 1)
        : (start = mid + 1)
      : 
      target >= nums[mid] && target <= nums[end]
      ? (start = mid + 1)
      : (end = mid - 1);
  }
  return -1;
};

参考

33. 搜索旋转排序数组