前端工程师leetcode算法面试必备-二分搜索算法（上）_2023-03-15

一、二分搜索算法

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种难度的总结篇（简单难度，中等难度以及困难难度）。在简单难度中，会介绍该算法的基本知识与实现，另外两个难度，着重讲解解题的思路。