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

一、二分搜索算法

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原文地址:https://segmentfault.com/a/1190000043393248

%s 个评论

要回复文章请先登录注册