什么是折半查找

折半查找（Binary Search）又称为二分查找。它要求数据序列呈线性结构，也就是经过排序的。对于没有经过排序的数据，可以通过排序算法进行预排序，然后进行折半查找的操作。

注意 折半查找方法要求查找表的数据是线性结构保存，并且还要求查找表中的数据是按关键字由小到大有序排列。

折半查找的具体过程是：假设有n个元素的查找表，首先计算位于查找表中间位置元素的序号m（m=n/2），取s[m]的关键字与给定值key进行比

较。比较结果有3种可能：

（1）若s[m]=key，表示查找成功。

（2）若s[m]>key，表示关键字key只可能在查找表的前半部分（因查找表中的数据是按从小到大的顺序排列），则在前半部分继续进行折半查

找。

（3）若s[m]<key，表示关键字key只可能在查找表的后半部分，则在后半部分继续进行折半查找。

**技巧 ****从上面的过程可看出，折半查找是一种递归过程。每折半查找一次，可使查找范围缩小一半，当查找范围缩小到只剩下一个元素，而该元素仍与关键字不相等，则说明查找失败。

在最坏的情况下，折半查找所需的比较次数为O（nlog 2 n），其查找效率比顺序查找法要快很多。

例如，有以下数据：

6，12，28，37，54，65，69，83，90，92

若要查找关键字37，则查找过程如下：

从上面的查找过程可看出，通过4次比较，可找到关键字37所在的位置。 

再例如，若要查找关键字66，其查找过程如下：

从上面的过程可看出，通过4次比较，当查找范围缩小到只剩一个元素，仍没有找到指定关键字，说明查找失败。