写点什么

前端工程师 leetcode 算法面试必备 - 二分搜索算法(上)

作者:js2030code
  • 2022-12-20
    浙江
  • 本文字数:1181 字

    阅读完需:约 4 分钟

一、二分搜索算法

1、简介

  二分搜索是一种在有序数组中查找某一特定元素的搜索算法。



  二分搜索算法的时间复杂度为 O(log n),相比较顺序搜索的 O(n) 时间复杂度,它要快很多。


  例如,在一个长度为一百万的有序数组中,采用顺序搜索,最坏的情况需要执行一百万次,而二分搜索算法只需要二十次!


  从上图,读者可以很容易发现,二分搜索的关键就是通过目标值与中间值的比较,将搜索区间缩小一半,这也是为什么有序数组是二分搜索算法的重要前提。

2、代码实现

  由前文可知,二分搜索并不是一个特别复杂的算法,但是想通过代码正确地实现它,并不是一件易事。


  首先要求出数组的中间下标(整数),从而获取到中间值:


  const mid = Math.floor((start + end) / 2)
复制代码


  读者可能第一时间想到的就是上述写法,但是在一些极端的情况,start + end 可能直接超出最大的安全整数,所以更加的谨慎的写法如下:


  const mid = Math.floor(start + (end - start) / 2)
复制代码


  最后就是搜索区间如何不断地缩小一半,对于很多初学者来说,经常会将其写成一个死循环,这里建议保持搜索区间左闭右开的写法:


while (start < end) {
const mid = Math.floor(start + (end - start) / 2)
if (arr[mid] < target) {
start = mid + 1
} else {
end = mid
}
}
复制代码

二、LeetCode 实战

1、744. 寻找比目标字母大的最小字母

  这道题目主要考察二分搜索算法的基本实现:



2、367. 有效的完全平方数


  这道题目需要如下两个技巧:


  • 如果 num 为完全平方数,那么能形成该完全平方数的整数必定存在 [1, num) 区间;

  • 取得 [1, num) 区间的中间值时,需要进行平方运算后再与 num 比较;



参考视频:传送门


类似解题思路的题目还有【69. x 的平方根】和【441. 排列硬币】。

3、852. 山脉数组的峰顶索引

  仔细读题之后,你会发现给定的数组并非有序数组,但是需要查找的目标数字恰巧处于一个很特殊的位置,当我们从当前区间查找到中间值时,可以通过与前一个数或者后一个数的比较,来判断当前中间值处于递增还是递减区间,从而判断峰值处于左半区间还是右半区间:



6、475. 供暖器


  这道题的难点在于是否读懂了题意:找到一个最小半径使得加热器覆盖所有房屋。


  那么最简单的解法就是遍历所有房屋的同时,遍历加热器找出距离该房屋的最小距离,那么所有房屋中的最大距离即为加热器覆盖的最小半径,那么整个过程的时间复杂度就是 O(n*m),对于加热器的搜索可以采用二分搜索算法优化,那么时间复杂度可以优化为 O(nlog m):



写在最后


  算法作为计算机的基础学科,用 JavaScript 刷,一点也不丢人ε=ε=ε=┏(゜ロ゜;)┛。


  本系列文章会分别给出一种算法的 3 种难度的总结篇(简单难度,中等难度以及困难难度)。在简单难度中,会介绍该算法的基本知识与实现,另外两个难度,着重讲解解题的思路。


  如果本文对您有所帮助,不要忘记点赞或者关注哟!


用户头像

js2030code

关注

还未添加个人签名 2022-09-14 加入

还未添加个人简介

评论

发布
暂无评论
前端工程师leetcode算法面试必备-二分搜索算法(上)_JavaScript_js2030code_InfoQ写作社区