33.搜索旋转排序数组

链接：33.搜索旋转排序数组
难度：Medium
标签：数组、二分查找
简介：假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组  [0,1,2,4,5,6,7]  可能变为  [4,5,6,7,0,1,2] )。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回  -1 。

题解 1 - javascript

• 编辑时间：2020-04-27
• 执行用时：68ms
• 内存消耗：33.8MB
• 编程语言：javascript
• 解法介绍：直接使用内置 indexOf。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  return nums.indexOf(target);
};

题解 2 - javascript

• 编辑时间：2020-04-27
• 执行用时：72ms
• 内存消耗：33.9MB
• 编程语言：javascript
• 解法介绍：二分查找进行判断是否有转折点。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  const len = nums.length;
  if (len === 0) return -1;
  let first = 0;
  let last = len;
  if (nums[last - 1] > nums[first]) {
    return search(first, last);
  } else
    while (first < last) {
      if (last - first === 1 && nums[first] !== target) return -1;
      const mid = (last + first) >> 1;
      // console.log("======");
      // console.log("first", first);
      // console.log("last", last);
      // console.log("mid", mid);
      const midNum = nums[mid];
      const firstNum = nums[first];
      if (midNum === target) return mid;
      if (midNum > firstNum) {
        if (target >= firstNum && target < midNum) return search(first, mid);
        else first = mid + 1;
      }
      if (midNum < firstNum) {
        if (target > midNum && nums[last - 1] >= target) return search(mid, last);
        else last = mid;
      }
    }
  return -1;
  function search(first, last) {
    // console.log("======");
    // console.log("search", first, last);
    if ((last - first === 1 && nums[first] !== target) || first === last) return -1;
    const mid = (last + first) >> 1;
    const num = nums[mid];
    if (num === target) return mid;
    else if (num < target) {
      return search(mid + 1, last);
    } else {
      return search(first, mid);
    }
  }
};