一、二分搜索算法
1、简介
二分搜索是一种在有序数组中查找某一特定元素的搜索算法。
在这里插入图片描述二分搜索算法的时间复杂度为 O(log n)，相比较顺序搜索的 O(n) 时间复杂度，它要快很多。
例如，在一个长度为一百万的有序数组中，采用顺序搜索，最坏的情况需要执行一百万次，而二分搜索算法只需要二十次！
从上图，读者可以很容易发现，二分搜索的关键就是通过目标值与中间值的比较，将搜索区间缩小一半，这也是为什么有序数组是二分搜索算法的重要前提。
2、代码实现
由前文可知，二分搜索并不是一个特别复杂的算法，但是想通过代码正确地实现它，并不是一件易事。
首先要求出数组的中间下标（整数），从而获取到中间值：
代码语言：text复制 const mid = Math.floor((start end) / 2)读者可能第一时间想到的就是上述写法，但是在一些极端的情况，start end 可能直接超出最大的安全整数，所以更加的谨慎的写法如下：
代码语言：javascript复制 const mid = Math.floor(start (end - start) / 2)最后就是搜索区间如何不断地缩小一半，对于很多初学者来说，经常会将其写成一个死循环，这里建议保持搜索区间左闭右开的写法：
代码语言：text复制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种难度的总结篇（简单难度，中等难度以及困难难度）。在简单难度中，会介绍该算法的基本知识与实现，另外两个难度，着重讲解解题的思路。
如果本文对您有所帮助，不要忘记点赞或者关注哟！
