704. 二分查找

方法1 「暴力解法」

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

描述

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

方法2 「二分查找」

var search = function(nums, target) {
  let l = 0, r = nums.length - 1;
  while(l <= r) {
    const mid = (r - l >> 1) + l;
    if (nums[mid] === target) return mid;
    else if (nums[mid] < target) l = mid + 1;
    else r = mid - 1;
  }
  return -1;
};

描述

初始情况下，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 「歪门邪道」

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

描述

• MDN Array.prototype.indexOf()

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

类似例题

733. 图像渲染

方法1 DFS

var floodFill = function (image, sr, sc, newColor) {
  const row_num = image.length, // 行数
    col_num = image[0].length, // 列数
    start_color = image[sr][sc]; // 开始颜色
  if (start_color === newColor) return image;
  // 递归上色
  const fill = (i, j) => {
    if (i < 0 || i >= row_num || j < 0 || j >= col_num || // 越界
      image[i][j] !== start_color) { // 不是开始颜色
      return;
    }
    image[i][j] = newColor;
    fill(i - 1, j); // 上
    fill(i + 1, j); // 下
    fill(i, j - 1); // 左
    fill(i, j + 1); // 右
  }
  fill(sr, sc); // 从初始坐标开始上色
  return image;
};