学步园

提一个有趣的问题：如果数组中有多个元素是v，上面的函数返回的是哪一个下标呢？下面的程序返回它出现的第一个位置。如果不存在，返回这样一个下标i：在此处插入v，（原来的元素A[i],A[i+1]....，全部往后移动一个位置）后序列仍然有序。

int lower_bound(int *A, int x, int y, int v)
{
	int m;
	while(x < y)
	{
		m = x+(y-x)/2;
		if(A[m] >= v) y = m;
		else x = m+1;
	}
	return x;
}

简要的分析：

A[m]= v：至少已经找到一个，而左边可能还有，因此区间变为[x,m]。

A[m]>v：所有位置不可能在后面，但有可能是m，因此区间变为[x,m]。

A[m]<v：m和前面都不可行，因此区间变为[m+1,y]。

合并一下：A[m]>=v时新区间为[x,m]; A[m]<v时新区间为[m+1,y]。这里有一个潜在的危险：如果[x,m]或者[m+1,y]和原区间相同，将发生死循环。不过这不会发生，留给大家思考。

类似的upper_bound的程序，当v存在时，返回它出现的最后一个位置的后面一个位置。如果不存在，返回这样一个下标i：在此处插入元素v（原来的元素A[i],A[i+1]....，全部往后移动一个位置）后学仍然有序。

int lower_bound(int *A, int x, int y, int v)
{
	int m;
	while(x < y)
	{
		m = x+(y-x)/2;
		if(A[m] <= v) x = m+1;
		else y = m;
	}
	return x;
}

这样，对二分的讨论就相对比较完整了，设low_bound和upper_bound的返回值分别为L和R，则v出现的子序列为[L,R)。这个结论当v不在时也成立：此时L=R，区间为空。