二分查找

二分查找 1 2 3 4 5 6 6 6 7 8 9

数组a中第一个 ==(⇐) t的数

// 数组下标从0开始, 从1则 l = 0, r = n + 1
int l = -1, r = n;
while(l + 1 != r)
{
	int mid = l + r >> 1;
	if(a[mid] < t)
		l = mid;
	else 
		r = mid;
}
// 当所有数都小于t时, r会为n, 当没有等于t的数时,r为第一个大于t的数, 当所有数都大于t时, r为第一个数
if(r != n && a[r] == t) return r;
else return -1;

数组a中最后一个 ==(>=) t的数

int l = -1, r = n;
while(l + 1 != r)
{
	int mid = l + r >> 1;
	if(a[mid] <= t)
		l = mid;
	else
		r = mid;
}
// 当所有数都小于t时或没有数等于t时, l为 从后往前第一个小于t的数, 当所有数都大于t时, l 为 -1
if(l != -1 && a[l] == t) return l;
else return -1;

这种实现有几个明显的优点：

1. 统一的循环终止条件 l + 1 != r，确保搜索区间最终缩小到相邻的两个位置
2. 明确的边界初始化 l = -1, r = n，避免了数组访问越界
3. 更容易适应”第一个满足条件”或”最后一个满足条件”的查找场景
4. 对返回值进行额外检查，处理目标值不存在的情况