1. 二分查找

LeetCode 第 704 题 二分查找

题目

给定一个 n 个元素 有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。 n 将在 [1, 10000]之间。 nums 的每个元素都将在 [-9999, 9999]之间。

解题思路

本题重点：

1. 数组是升序的
2. 数组元素不重复，并且是整数

升序并且不重复，那么就相当于一个索引，如果有数据库经验，那么索引是查找数据最快的方法，那么二分查找也是索引的常用手段。

首先我们第一步，把数组的头尾各自设置一个游标：left 和 right, 并且找到最中间的位置 mid，来做二分查找。

function search(nums, target) {
  let left = 0
  let right = nums.length - 1
  let mid

  while(left <= right) {}
}

重点说一下 while 循环的条件，为什么是 left <= right, 而不是 left < right，假设 nums 长度是3（例如：[1,3,5]），那么二分后，中间肯定是索引 1，两边各剩下一个元素，那么这时候 left 和 right 必然是相等的，所以要考虑划分到只剩一个的时候左右相等的情况。

接下来我们来寻找二分的位置 mid

function search(nums, target) {
  let left = 0
  let right = nums.length - 1
  let mid

  while(left <= right) {
    // 头尾相加 / 2 取整数部分
    mid = Math.floor((left + right) / 2)
    // 如果这个中间的值刚好等于目标值，即找到了 返回这个索引
    if (nums[mid] === target) {
      return mid
    } else if (target > nums[mid]) {
      // 如果目标值大于中间值，说明目标值在右边半部分，这时候右边指针不动，左边指针移动到 mid + 1
      left = mid + 1
    } else {
      // 最后这种是目标值小于中间值，右指针移动
      right = mid - 1
    }
  }

  // 如果遍历没有找到，则返回 -1
  return -1
}