[C++知识库]C++实现二分查找

问题描述

给定一个升序数组，在数组中查找特定元素。

代码

下面这段代码用来搜索第一个出现的目标值，存在则获取目标位置，不存在则获取目标应当插入的位置

bool search(vector<int> a, int target, int& pos){ //  a是有序数组，target是目标值
	int left = 0, right = a.size() - 1;
	pos = left + (right - left) / 2; //  不写(right + left) / 2是为了防止整型溢出
	while(left < right){
		if(a[pos] < target)left = mid + 1; //  +1可防止无限循环 
		else right = mid; //  不能改为mid - 1，因为区间内必须包含目标
		pos = left + (right - left) / 2;
	}
	if(a[pos] == target)return true; //  判断是否存在目标值 
	else if(a[pos] < target)++pos; //  target插入数组外的特殊情况
	return false;
}

如果要搜索查找一个出现的目标值，注意pos的上下取整，稍作修改即可。