二分查找

#include <stdio.h>

int bsearch1(const int a[], int len, int target)
{
	int left, right, middle;
	if (len <= 0) return -1;
	left = 0;
	right = len - 1;
	while (left < right) {
		middle = (left + right) / 2;
		if (target <= a[middle]) {
			right = middle;
		} else {
			left = middle + 1;
		}
	}
	return a[left] == target ? left : -1;
}

int bsearch2(const int a[], int len, int target)
{
	int left, right, middle;
	left = 0;
	right = len - 1;
	while (left <= right) {
		middle = (left + right) / 2;
		if (target == a[middle]) {
			return middle;
		} else if (target < a[middle]) {
			right = middle - 1;
		} else {
			left = middle + 1;
		}
	}
	return -1;
}

int main()
{
	int a[7] = { 1, 3, 5, 7, 9, 11, 13 };
	int len = 7;
	int n = 16;
	int i = 0;
	for (i = 0; i < n; ++i) {
		printf("find %d ? %d\n", i, bsearch1(a, len, i));
		/* printf("find %d ? %d\n", i, bsearch2(a, len, i)); */
	}
	return 0;
}

上面列出了两个二分查找的函数 bsearch1 和 bsearch2，两者的主要差别是循环内的比较。

bsearch1 循环内只需要比较一次。但由于循环内没有相等的比较，所以即使 a[middle] 已经是所要查找的值，但也不能确定，仍要继续比较下去。正是这样的查找方式，也使得 bsearch1 是一种比较“稳定”的二分查找。这里的稳定是指：1.查找所用的比较次数接近于log2(N)；2. 找查得到的位置总是target第一次出现的的位置。

bsearch2 循环内需要1或2次的比较，这取决于a[middle]的值是否是target。这样也使得 bsearch2 的查找次数会变化比较大，较不稳定。而且查找得到的位置也不一定的是target第一次出现的位置，而且如果数组发生变化时，如在数组最后增加或删除元素，虽然target的位置没有发生过变化，但查找target得到的位置也会不同，当然，如果数组中不存在重复元素，那就不会出现这个问题。

本文出自 “chhquan” 博客，请务必保留此出处http://chhquan.blog.51cto.com/1346841/1567646

二分查找