18.2 折半查找

18.2 折半查找

从一组排好序的序列里找出某个元素的位置，可以有比线性查找更快的方法。

#include <stdio.h>

#define LEN 8
int a[LEN] = {1, 2, 2, 2, 5, 6, 8, 9};

int binarysearch(int number)
{
	int mid, start = 0, end = LEN - 1;

	while (start <= end) {
		mid = (start + end) / 2;
		if (a[mid] < number)
			start = mid + 1;
		else if (a[mid] > number)
			end = mid - 1;
		else
			return mid;
	}
	return -1;
}

int main(void)
{
	printf("%d\n", binarysearch(5));
	
	return 0;
}

由于这个序列已经从小到大排好序了，每次取中间的元素和待查找的元素比较，如果中间的元素比待查找的元素小，就说明“如果待查找的元素存在，一定位于序列的后半部分”，这样就把搜索范围缩小到后半部分，然后再次使用这种算法迭代。

这种“每次将搜索范围缩小一半”的思想称为折半查找(Binary Search)。