2012年07月 存档

编程珠玑 第四章 习题解答

2012年07月8日,星期日

1.为了保证范围不超过范围,我们需要在初始化的时候,让变量不超出范围。这样每次循环得到的新的范围是慢慢缩小的,不会越界。

2.迭代的二分查找。

int bs( int *a, int l, int r, int v ){
	while( l <= r ){
		if( a[l] == v ) return l;
		int mid = (l+r)/2;
		if( a[mid] < v ) l = mid+1;
		if( a[mid] == v )r = mid;
		if( a[mid] > v ) r = mid-1;
	}
	return -1;
}

这个二分可以返回所需要查询的元素第一次出现的位置,如果不存在,则返回-1.在每个循环内,我们假定元素第一次出现的范围是闭区间[l,r]内,当循环体内语句执行完之后,我们得到了一个新的区间。新的区间的范围是一直在收敛的(不会存在r,l执行完循环之后大小没有变化。),所以程序可以终止,得到正确结果。

3.将2的二分程序改写成递归的形式。

int bss( int *a, int l, int r, int v ){
	if( l > r ) return -1;
	if( a[l] == v ) return l;
	int mid = (l+r)/2;
	if( a[mid] < v ) return bss( a, mid+1, r, v );
	if( a[mid] == v )return bss( a, l, mid, v );
	if( a[mid] > v ) return bss( a, l, mid-1, v );
}

(更多…)