leetcode

简单数组二分查找

35. 搜索插入位置
278. 第一个错误的版本

方法1 暴力解法

  1. var search = function(nums, target) {
  2.   for (let i = 0; i < nums.length; i++) {
  3.     const item = nums[i];
  4.     if (item === target) return i;
  5.     else if (item > target) return -1;
  6.   }
  7.   return -1; // target 同学是最高的
  8. };

image.png

注解

image.png

nums 就好比是从矮到高的一队同学，target 就是要插入到这队同学中的一个新同学。
插入规则：target 只能插入到身高和他相同的那位同学所在的位置「返回该同学所在索引」，如果找不到该同学，那么他无法插入「返回 -1」。

方法2 二分查找

  1. var search = function(nums, target) {
  2.   let l = 0, r = nums.length - 1;
  3.   while(l <= r) {
  4.     const mid = (r - l >> 1) + l;
  5.     if (nums[mid] === target) return mid;
  6.     else if (nums[mid] < target) l = mid + 1;
  7.     else r = mid - 1;
  8.   }
  9.   return -1;
  10. };

image.png

注解

image.png

初始情况下，left 指向头，right 指向尾。通过 left 和 right 计算出中间指针 mid 的位置，由于数组已经是有序的了，所以每次循环时，通过比较 nums[mid] 和 target 之间的大小，即可不断缩小目标值 target 可能存在的区间。

  • 问：继续循环的条件，是否可以改为 l < r？

不可
设想一种极端情况，nums.length === 1，并且 nums[0] === target。
这种情况下，应该返回的是 0，但实际返回的是 -1。

  • 问：每次缩减区间时，都要将 l = mid + 1 或 r = mid - 1，是否可以改为 l = mid 或 r = mid？

不可
按照以上程序的逻辑，当 l 和 r 之间的差值小于 2 时，那么 mid 将始终指向 l。
输入：nums = [1, 2], target = 2
输出：1
实际：死循环

方法3 indexOf

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

image.png

注解

MDN Array.prototype.indexOf()

题目描述的其实就是 JavaScript 数组原生 api indexOf 的功能。

如果仅仅是为了解决问题的话，使用 JavaScript 完全可以使用 indexOf 这个原生的数组 api 来解决。并且在实际开发中，若真遇到此需求，应该也会首先想到使用它。