不一样的二分查找-只比较一次的2分查找实现

[list]

正常进行2次比较的二分查找实现,取列表中点值，（1）先比较x是否小于v[mid]，若小于则说明在mid的左侧，（2）继续比较x是否大于v[mid],若大于则说明在mid的右侧

（3）否则mid即为x的位置

int binsearch(int x, int v[], int n) {
	int low, high, mid;
	low = 0;
	high = n - 1;
	while(low <= high) {
		mid = low + high;
		if (x < v[mid]) {
			high = mid - 1;
		}
		else if (x > v[mid]) {
			low = mid + 1;
		}else {
			return mid;
		}
	}
	return -1;
}

只进行1次比较的二分查找实现，取列表中点值，（1）比较x是否小于v[mid],若小于则说明在mid的左侧 (2)否则记录下当前mid的值，继续往右比较

(3)查找结束后，对比记录下的位置所对应的值是否等于x

int binsearch2(int x, int v[], int n) {
	int low, high, mid, cur;
	cur = -1;
	low = 0;
	high = n - 1;
	while (low <= high) {
		mid = (low + high) / 2;
		if (x < v[mid]) {
			high = mid -1;
		}else {
			cur = mid;
			low = mid + 1;
		}
	}
	return (cur != -1 && v[cur] == x)? cur : -1;
}

[/list]

第二种方式减少了循环内的比较次数，但是可能增加本身循环的次数（第一种方式，在mid=x时就可以退出循环了，但第二种的循环结束条件为low 〉high）但因为是o（logN）所以循环次数增加的不多，还没进行实际的性能测试，以后补上。