二分查找

发表于 分类于 阅读次数：

本篇博客简单介绍一下二分查找算法及其框架

二分查找

二分查找的思路其实很简单，无非就是一堆数据过来，你就不断分分分分分，就能把一堆数据分成仅剩一个，但细节真的很多，一个不注意就会漏掉数据，这里我们利用二分查找的一个固定框架来简单的介绍一下这些细节问题。
先直接上代码框架

1
2
3
4
5
6
7
8
9
10
11
12
13
const binarySearch = (nums,target) => {
    let left = 0;
    let right = ...;
    while(...) {
        let mid = Math.floor(left + (right - left) / 2); // 防止left + right 太大导致计算溢出
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ... }
}
    return ...; }

记住，写二分查找千万不能偷懒直接写else，要用else if 写明每一个情况。当然十分自信的话用else来简化代码也不是不可以,然后利用这个框架，我们写一个最简单的查找数组里面的元素。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
const binarySearch = (nums, target) => {
  let left = 0;
  let right = nums.length - 1;
  while(left <= right){
    let mid = Math.floor(left + (right - left) / 2);
      if(nums[mid] == target){
        return mid
      }
      else if(nums[mid] < target) left = mid + 1;
      else if(nums[mid] > target) right = mid - 1;
  }
  return -1 
}

然后注意几点， while 里面是 <= ,因为这里初始化right是length -1，表示数组最后一个值的索引，所以可以取等号，直接就是二分查找需要考虑的一个重点问题 **边界问题**
这就看具体题型了，因为这题属于是闭区间【】，数组的头和尾都有可能是查找的值，取等号是没问题的，有些左闭右开区间 【 ）就要考虑是否该用<来代替<=了。这里我们再说一下终止条件和搜索区间的联系。
当while取 <= 时，终止条件是 left > right, 大概就是让你在[3,2]中找一个值，这根本不可能找到对吧，然后 < 的终止条件是left == right情况就是在(2,2)中找，也找不到，因为是开区间取不到2。

再然后，为什么left和right要是mid + 1/ - 1。 还是从搜索区间来看吗，当我们发现mid不是我们要找的值，那mid是不是就不用找了？那搜索区间就理所应当的是[mid + 1,right],[left,mid - 1]。
至此二分查找应该可以有个基本的理解了，但这个框架有缺陷，比如给个有序数组 nums = [1,2,2,2,3]，想找2，确实能找到，但是只能找到最中间的2，左右两边2是不可能查的到的，哎，这就很烦。