二分查找（二分查找）简介以及C/C++代码实现

1。算法介绍

二分查找也称为二分查找，大多数人喜欢称之为二分查找。这是一种更有效的搜索方法。但半查找要求线性表采用顺序存储结构，表中的元素必须按关键字排序。注意，必须按顺序订购，但有一种特殊情况不必按顺序处理，即上一节中介绍的产品从一堆重量标准为 的产品中选择并找到单个缺陷产品10. 在这种特殊的数据情况下，也可以使用二分查找。

2。具体计算

二分查找的基本思想是将n个元素分成大致相等的两部分，然后将a[n/2]与x进行比较。如果 x=a[n/2] 那么当找到 x 时，算法终止；如果 xa[n/2] 则继续在数组的右半部分查找 x，然后 .

总共有 n 个元素，

后面依次是 n、n/2、n/ 4、....n/2^k（接下来要处理剩下的元素个数），其中k为循环次数

因为n/2^k四舍五入>=1，即n /2^k=1 可以通过 k=log2n 得到，（是以 2 为底的 n 的对数）

所以时间复杂度可以表示为 O(log2n) [对数的时间复杂度基本可以得到类似的方式，所以计算时间复杂度的过程如图]

3。实现代码

代码仅供参考