折半查找
折半查找又叫二分查找，首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
折半查找过程演示，如下图所示，表中元素按升序排列：
假如要查找一个数据253。那么首先查看表中中间位置(0+8)/2即位置为4的元素：53。因为253比53要大，所以丢弃表中0到4的子表数据，剩下5到8的字表数据。然后再计算5到8的子表的中间位置(5+8)/2即6的位置的元素：101。因为253比101的数据要大，所以丢掉5到6子表中的元素，剩下7到8子表的元素。然后找到7到8中间位置(7+8)/2即7所在位置的元素：253，二者相等，那么查找成功，即所在位置为7。
假如要查找一个为3的数据。那么首先查看表中中间位置(0+8)/2即位置为4的元素：53。因为3比53要小，所以丢掉4到8之间的子表元素，保留0到3之间的子表元素。然后在计算0到3之间的中间元素(0+3)/2即1所在位置的元素：9。因为3比9要小，所以丢掉1到3之间子表元素，留下0位置的元素1，但3比1要大。所以整个表查完，没有找到该元素，查找失败。
下面是折半查找算法：
//a为存放数据的有序表，n为数据元素个数，k为要查找的元素
int BinSearch(int a[], int n, int k)
{
int low, high, mid, find, i;
find = 0;
low = 0;
high = n-1;
while (low <= high && !find)
{
mid = (low + high)/2;
if (a[mid] < k)
low = mid + 1;
else if (a[mid] > k)
high = mid - 1;
else
{
i = mid;
find = 1;
}
}
if (!find)
i = -1;
return i;
}
递归版本：
int IterBiSearch(int data[], const int x, int beg, int last)
{
int mid = -1;
mid = (beg + last) / 2;
if (x == data[mid])
{
return mid;
}
else if (x < data[mid])
{
return IterBiSearch(data, x, beg, mid - 1);
}
else if (x > data[mid])
{
return IterBiSearch(data, x, mid + 1, last);
}
return -1;
}
int BinSearch(int a[], int n, int k)
注意：折半查找必须满足两个条件：一，元素必须是连续存储；二，元素必须有序。时间复杂度：O(logn)
