二分搜索算法

2020-04-19 by 杜宏伟

在数组有序的条件下,二分搜索可以把时间复杂度从O(n)下降到O(logn),所以二分算法意义重大。

简单来说,二分法每次会把问题规模减少一半。算法不好处理的地方在于边界。为了可以快速准确写出二分算法,推荐的做法是记一套模板。记一套模板并不是死记,而且真正理解了每一句代码,以这套模板为基础,应对各种变化。

二分算法模板推荐

function binarySearch(arr, target) {
  //定义左边界
  let low = 0
  //定义右边界
  let high = arr.length

  while (low < high) {
    //获取中间索引
    let mid = low + ((high - low) >> 1)
    if (arr[mid] >= target) {
      high = mid
    }
    else {
      low = mid + 1
    }
  }
  return arr[low]
}

边界采用左闭右开 [1,2,3)。左边界大于等于,右边界小于。右边界的小于和下面的 low < high 配合使用保证low可以取到所有可能的值。取中间值的时候一定要 arr[mid] >= target, 大于等于很重要,保证arr[low]一定是小于target的,所以最后 arr[low]跳出循环的时候一定是target

取中间值有多种写法。我觉得移位看起来简洁一些,所以一直这样写。

let mid = low + ((high - low) >> 1)

也可以这样写,可读性好

let mid = low + Math.floor(((high - low) / 2))

但是不能这样写,因为(low+high)可能会溢出。

let mid =Math.floor((low+high)/2)

二分法典型应用

704. 二分查找

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

解法

直接用模板即可

let index= binarySearch(nums,target)
return index===undefeind?-1:index

367. 有效的完全平方数

给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。

说明:不要使用任何内置的库函数,如 sqrt。

解法

low,high不是直接给出,需要自己找到。找到之后套模板

let high = num+1

加 1 是为了让 low 可以有机会取到所有值.

/**
 * @param {number} num
 * @return {boolean}
 */
var isPerfectSquare = function(num) {
     //定义左边界
  let low = 0
  //定义右边界
  let high = num+1

  while (low < high) {
    //获取中间索引
    let mid = low + ((high - low) >> 1)
    if (mid*mid >= num) {
      high = mid
    }
    else {
      low = mid + 1
    }
  }
  return low*low===num
};

367. 爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有 N 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开了,将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 K 根。如果这堆香蕉少于 K 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K(K 为整数)。

解法

这次的二分线索更加隐蔽些。要读懂题意,因为内容比较多,所以更需要仔细读题。

分析:珂珂吃香蕉的速度候选值可以组成一个数组。珂珂吃香蕉的速度越快,在H小时内能吃掉的香蕉越多,反之越少。因为是单调递增,所以可以用二分查找。

最小速度肯定是 1

//定义左边界
let low = 1

因为每小时至多只能吃一堆,所以如果保证每小时可以吃掉一堆,就需要每小时间至少要吃掉数量最大的一堆。因为我们的模板是右开,所以需要加 1

//定义右边界
let high = Math.max(...piles)+1

最后用一个函数来判断取值是否合适。

/**
 * @param {number[]} piles
 * @param {number} H
 * @return {number}
 */
var minEatingSpeed = function(piles, H) {

  //定义左边界
  let low = 1
  //定义右边界
  let high = Math.max(...piles)+1

  while (low < high) {
    //获取中间索引
    let mid = low + ((high - low) >> 1)
    if (helper(mid) <= H) {
      high = mid
    }
    else {
      low = mid + 1
    }
  }
  return low

  function helper(n){
    return piles.reduce((sum,item)=>sum+=Math.ceil(item/n),0)
  }
};

总结

虽然二分可以解决的问题很多,但典型的纯二分这三个题就代表了。最关键的是要找到low,high, 取值和答案之间是不是单调递增或递减。有的题目虽然整体不是单调递增或递减,但用二分处理的子问题一定是单调递增或递减

熟练掌握一套模板非常重要,这套模板是左闭右开,让low无限逼近答题,最后 low+1即是答案。

模板需要灵活运用。因为是右开,所以如果一上来就需要判断最右值nums[high] 会导致取不到值。两个解决办法。

  1. 用左值判断,并不推荐。推荐一直用右值,这样更不容易出错。左右思维是相反的,如果右值判断习惯了,突然换左值,思考速度会变慢,会不习惯。
  2. 如果必须判断右值 high 不要加 1。这样会导致low可能取不到high,所以最后单独判断一下 high

注意,不要把low<high修改为low<=high,这样可能会导致无限循环。

本套二分模板要点

  1. 模板能动的部分,low,high,不能动的 low<high
  2. 优先用右值判断,让左边无限接近答案,但不会等于答案。
  3. [low,high) 包含所有解,low+1 就是答案。
  4. [low,high] 会漏掉最右解,一开始就单独判断最右解,然后然后就转化为[low,high) 和第2条一样了。

我叫杜宏伟,前端开发。

一直想写博客,在2018的年的最后几天,终于上线了。

对于前端开发,一个特点就是太零散,很容易会了后面忘了前面,所以归纳总结很重要。再有就是分享,做前端好多年,以前都是看你们写的文章, 现在我也开始写一些,希望可以帮到入行的小伙伴。微信号 duhongwei5775

欢迎转载,只需注明作者,出处即可

版权说明:署名 4.0 国际(CC BY 4.0)