原文链接：https://blog.csdn.net/Luckyzhoufangbing/article/details/110389523
（一）定义
二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。
二分法查找的思路如下：
（1）首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。
（2）如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤（1）的操作。
（3）如果某一步数组为空，则表示找不到目标元素。
二分法查找的时间复杂度O(logn)
（二）适用条件
（1）排好序的数组
（2）线性表具有有随机访问的特点（例如数组）可以通过下标 或者 key 直接取到，链表就不具备这样的特点
（3）线性表能够根据中间元素的特点推测它两侧元素的性质，以达到缩减问题规模的效果
（三）注意的几点
1. 双指针中间数值 index
var midIndex = parseInt((right + left) / 2)
2. 循环条件
while (left <= right)
2. 如果数组中没有要找的元素
最终 left 比 right 大，应该插入 left 所在的位置
（四）总结
二分查找一般由三个主要部分组成：
（1）预处理 —— 如果集合未排序，则进行排序。
（2）二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。
（3）后处理 —— 在剩余空间中确定可行的候选者。
三个模版：https://leetcode-cn.com/leetbook/read/binary-search/xewjg7/