一、二分搜索算法
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 种难度的总结篇（简略难度，中等难度以及艰难难度）。在简略难度中，会介绍该算法的基本知识与实现，另外两个难度，着重解说解题的思路。
如果本文对您有所帮忙，不要遗记点赞或者关注哟！