乐趣区

leetcode不定期刷题33-搜索旋转排序数组

来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array

题目概述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
(例如,数组 [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。
然后我就直接写下了

var search = function(nums, target) {return nums.indexOf(target);
};

运行之后通了,提交之后也通了,执行时间 68ms,内存消耗 33.7MB。
完美的开始,不过在仔细审题之后,发现一个问题,题目要求复杂度必须是 O(log n) 级别,那意思就是必须得使用二分法来做。那么上面的答案就没有意义了。
那么重新开始思考。二分法很简单,就是每次都二分数组,然后在符合条件的数组中进行下一步的二分查找。
将数组一分为二之后,存在两种可能,一边是顺序的,一边是旋转的,那么就需要将 target 值与左右中间做间隔的值以及两个数组的两端值进行比较。从而判断出要继续在哪个数组中继续寻找。

 实例
nums = [4,5,6,7,8,9,0,1,2], target = 0

第一步:取数组中间值,将数组一分为二。

// 设置初试下标值:left=0;
right = nums.length;
mid = ~~((left + right)/2)
// 二分数组那么这个时候 mid=4
[4,5,6,7] 
8 
[9,0,1,2]

第二步:mid 值跟两边数组的首尾进行比较

存在以下几种情况

  • nums[mid] === target

中间值等于目标值,此时可以直接返回 mid

  • nums[mid]>target && nums[left] <= target

中间值比目标值 target 大并且左边数组第一个值小于 target,那么说明左边数组是存在旋转的,并且目标值就在这个数组中,这个时候需要继续在左边数组中查找,这个时候 left 不变,right 变成了 mid-1;

  • nums[mid]<target && nums[right]>=target

中间值比目标值 target 小并且右边数组最后一个值大于等于 target,说明 target 值在右边数组中,所以需要在右边的数组中继续查找。此时 left 变成了 mid+1,right 不变。

  • nums[mid]<target && nums[right]<target
  • nums[mid]>target && nums[left] > target

这两种情况下,都是没有确定值在哪边,所以讲 left+ 1 或者 right- 1 进行进一步的查找。
就这样一步一步查找知道最终找到值。用递归可以解决这个问题。

所以代码如下:


/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {var bs = (left,right)=>{const mid = ~~((left + right)/2);
          if(left > right)return - 1;
          if(nums[mid] === target){return mid;}else if(nums[mid]>target && nums[left] <= target){return bs(left,mid-1);
          }else if(nums[mid]>target && nums[left] > target){return bs(left+1,right);
          }else if(nums[mid]<target && nums[right]>=target){return bs(mid+1,right);
          }else if(nums[mid]<target && nums[right]<target){return bs(left,right-1);
          }
      };
      return bs(0,nums.length-1);
};
 运行结果:执行时间:68ms
内存消耗:33.9MB
退出移动版