二分查找算法实现（图解）与实例
当我们要从一个序列中查找一个元素的时候，二分查找是一种非常快速的查找算法，二分查找又叫折半查找。
它对要查找的序列有两个要求，一是该序列必须是有序的（即该序列中的所有元素都是按照大小关系排好序的，升序和降序都可以，本文假设是升序排列的），二是该序列必须是顺序存储的。
如果一个序列是无序的或者是链表，那么该序列就不能进行二分查找。之所以被查找的序列要满足这样的条件，是由二分查找算法的原理决定的。
二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
二分查找能应用于任何类型的数据，只要能将这些数据按照某种规则进行排序。然而，正因为它依赖于一个有序的集合，这使得它在处理那些频繁插入和删除操作的数据集时不太高效。这是因为，对于插入和操作来说，为了保证查找过程正常进行，必须保证数据集始终有序。相对于查找来说，维护一个有序数据集的代价更高。此外，元素必须存储在连续的空间中。因此，当待搜索的集合是相对静态的数据集时，此时使用二分查找是最好的选择。
二分查找算法的原理如下：
二分查找之所以快速，是因为它在匹配不成功的时候，每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快，而不像顺序查找那样，每次仅能排除一个元素。
二分查找法实质上是不断地将有序数据集进行对半分割，并检查每个分区的中间元素。
此实现过程的实施是通过变量left和right控制一个循环来查找元素（其中left和right是正在查找的数据集的两个边界值）。
二分查找的时间复杂度取决于查找过程中分区数可能的最大值。对于一个有n个元素的数据集来说，最多可以进行O(㏒₂n)次分区。对于二分查找，这表示最终可能在最坏的情况下执行的检查的次数：例如，在没有找到目标时。所以二分查找的时间复杂度为O(㏒₂n)。
参考：
https://www.html.cn/qa/other/23018.html
https://www.cnblogs.com/idreamo/p/9000762.html
基本算法——二分查找算法
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
1.条件
（1）必须采用 顺序存储结构 。
（2）必须按关键字大小有序排列。
2.步奏
（1）首先，假设表中元素是按升序排列，将表中间位置记录的 关键字 与查找关键字比较，如果两者相等，则查找成功；
（2）否则利用中间位置 记录 将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表；
（3）重复以上过程，直到找到满足条件的 记录 ，使查找成功，或直到子表不存在为止，此时查找不成功。
3.举例
有一组元素{1，2，3，4，5，6，7，8，9}，如何查到元素为3。
（1）找到数组中中间元素值5，不等于3，所以把数组分为{1，2，3，4}，{5，6，7，8，9}；
（2）因为5大于3，所以3在前一个数组{1，2，3，4}中查找，中间变量2，3比2大，所以在{3，4}中查询；
（3）查询到3=3，成功。
4.复杂度
最好的情况下，1次查询成功；最坏的情况下，查询到最后两个数或者最后也查不到相等数，时间复杂度为O(log2n)。
