一、基本概念
折半查找(Binary Search)，又称二分查找，查找效率高，但仅适用于顺序存储的有序表。其基本的思路如下：在一个有序表中，每次取中间记录数同目标值进行比较。若该记录数等于目标值，则查找成功；若大于目标值，则说明目标值在该查找表的左半区，此时我们往左半区进行查找；若小于目标值，则说明目标值在该查找表的右半区此时我们往右半区进行查找。如此往复，直至查找成功；若无和目标值相等的记录数，则查找失败。
注意，上述描述是基于升序查找表基础上进行分析的。
二、实现思路
我们首先需要定义三个指针Low , Mid , High ，分别指向查找区间的头、中、尾。
我们再定义一个有序的顺序表，如下：
我们设查找的目标值target = 21，基本流程如下：
1、Low = 1，指向12；High = 12，指向23；Mid = (Low + High) / 2
= 6 ，指向17。此时Mid指向17 < 21，我们需要将Low指针右移至Mid + 1 = 7，往右半区查找。
2、Low = 7 ，指向18；High = 12，指向23；Mid = (Low + High) / 2
= 9，指向20。此时Mid指向20 < 21，我们需要再次将Low指针右移至Mid + 1 = 10，往右半区查找。
3、Low = 10，指向21；High = 12，指向23；Mid = (Low + High) / 2
= 11，指向22。此时Mid指向22 > 21，我们需要将High指针左移至Mid - 1 = 10，往左半区查找。
4、Low = High = 10，指向21；Mid = (Low + High) / 2
= 10，指向21。此时Mid指向21 = 21，查找成功，目标值的位序就是Mid的值。
三、代码实现（C语言）
```
// 折半查找
int BitSearch(int *Arr , int Len , int Target)
{
int Low , High , Mid;
Low = 0;
High = Len;
while(Low <= High)
{
Mid = (Low + High) / 2; // 折半
if(Arr[Mid] == Target) // 查找成功
{
return Mid + 1; // 我们要返回的是位序
}
else if(Arr[Mid] > Target) // 中间值大于目标值
{
High = Mid - 1;
}
else // 中间值小于目标值
{
Low = Mid + 1;
}
}
return -1; // 查找失败
}
int main()
{
int Array[12];
// 生成有序数组
for(int i = 0 ; i <= 11 ; i++)
{
Array[i] = i + 12;
}
printf("查找表：");
for(int i = 0 ; i < 12 ; i++)
{
printf("%d\t" , Array[i]);
}
// 查找数值21的位序
int target = 21;
int Pos = BitSearch(Array , sizeof(Array) / sizeof(Array[0]) - 1 , target);
printf("\n");
if(target != -1)
{
printf("查找成功，数值%d的位序是：%d" , target , Pos);
}
else
{
printf("查找失败");
}
return 0;
}
```
四、效率分析
在数据结构中，我们都学过树这种数据结构。我们都知道，在一棵有n(n >= 0)个结点的完全二叉树中，树的深度k = + 1。折半查找的查找过程，也可以理解为一棵二叉排序树的构造过程。话不多说，直接上图
1、第一轮查找，Low = 1 ，High = 12，Mid = (Low + High) / 2
= 6，指向17。此时17 < 21，我们需要将Low指针右移至Mid + 1 = 7，往右半区查找。此时查找的状态如下：
2、第二轮查找，Low = 7，High = 12，Mid = (Low + High) / 2
= 9，指向20。此时20 < 21，我们需要继续将Low指针右移至Mid + 1 = 10，往右半区继续查找。此时查找状态如下：
3、第三轮查找，Low = 10，High = 12，Mid = (Low + High) / 2
= 11，指向22。此时22 > 21，我们需要将High指针左移至Mid - 1 = 10，往左半区查找。此时查找状态如下：
4、第四轮查找，Low = 10，High = 10，Mid = (Low + High) / 2
= 10，指向21.此时21 == 21，查找成功！此时的查找状态如下：
我们可以看到，在这棵二叉树中，查找成功的最坏情况是查找次数等于该树的深度k。我们都知道，一棵二叉树的最大深度为 + 1。所以在查找成功的情况下，折半查找的最坏时间复杂度为
。那么，其平均查找长度必然小于等于
。在这棵树中，折半查找的平均查找长度如下：
ASL(成功) = (1 * 2 + 2 * 4 + 3 * 5 ) / 12 = 25 / 12
当查找失败的时，查找位置会落在二叉树的空链域中。一棵有n个结点的二叉树有2n个空链域，所以查找失败的平均查找长度如下;
ASL(失败) = (3 * 3 + 4 * 10) / 13 = 49 / 13
完整二叉树如下（有那么一丝丝难看）：
