学步园

        二分查找是对已经排序好的序列进行查找。因为这个程序非常经典地简单又容易出错，所以在当着面试官纸上写程序的场合这个程序的命中率非常高。

        源码如下：

#include <iostream>
using std::cout;
using std::endl;

//xk> 二分查找
//xk>--------------------------------------------------
// 返回value在数组A中的索引
int
binarySearch(int A[], int N, int value)
{
	int low = 0;
	int high = N - 1;
	int mid;

	while(low <= high){
		// mid = (low + high) / 2;	// 这种写法容易溢出
		mid = low + ((high - low) >> 1);
		if(A[mid] > value)
		{
			high = mid - 1;
		}else if(A[mid] < value){
			low = mid + 1;
		}else{
			return mid;
		}
	}
	
	return -1;
}

int
main()
{
	int A[] = {0, 1, 2, 3, 4, 5, 6, 7};

	int n = binarySearch(A, 8, 4);
	cout << n << endl;

	return 0;
}

        上面的程序只是简单地实现了最基本的二分查找。下面来个高端的：

        找出一个有序(字典序)字符串数组arr中值等于字符串v的元素的序号，如果有多个元素满足这个条件，则返回其中序号最大的。

        int binSearch(char **arr, int b, int e, char *v);

#include <iostream>
using std::cout;
using std::endl;

int
binSearch(char **arr, int min, int max, char *v)
{
	int mid;
	//xk> 注意防止终止条件不可达
	// 若min为偶数，终止条件为min == max
	// 若min为奇数，终止条件为min == max - 1
	// while(min < max)或while(min <= max)都会出现死循环
	while(min < max - 1){
		//xk> 注意防止溢出
		mid = min + (max - min) >> 1;
		//xk> 因为要返回最大的序号，优先移动min，并且=0时也要继续移动
		if(strcmp(arr[mid], v) <= 0){
			//error> min = mid + 1;
			// 因为判断条件是<=0, 在等于时也会移动min
			// 这里不能加1，否则可能跳过已找到的，返回-1
			min = mid;
		}
		else{
			// 这里也不需要减1
			max = mid;
		}
	}
	if(!strcmp(arr[max], v)){
		return max;
	}else if(!strcmp(arr[min], v)){
		return min;
	}else{
		return -1;
	}
}

void
main()
{
	// 设计测试用例
}