【问题引入】

很多时候，简单的二分查找并不能满足我们的要求。
例如，我们要在下面的数据中查找第一个出现 $5$ 的位置。

存储下标   1 2 3 4 5 6 7 8 9
数值       3 5 5 5 5 5 5 5 8

如上所示，第一个数字 $5$ 出现在第 $2$ 个位置。我们称这类问题为二分查找下界，可以用在二分查找，也可以用在二分答案。整个思路和标准二分查找一样。

【步骤 $1$】

我们需要从 $[1,9]$ 中找数据 $5$，因此 $l=1,\ r=9$。由于 $l<r$，我们可以使用二分来查找。这样 $m=(l+r)/2=(1+9)/2=5$。
此时，$a[5]=5$，二分查找并没有完成，我们需要进一步缩小区域，看是否还有数据 $5$ 的存在。
根据二分的特性，$[6,9]$ 这个区间，肯定不会存在答案。答案只能在 $[1,5]$ 这个区间，注意 $a[5]$ 是可能的。
因此，我们使用 $m$ 的数据更新 $r$，即 $r=m$。也就是说，我们继续 $[l,r]$，即 $[1,5]$ 这个区间进行二分查找。

【步骤 $2$】

我们需要从 $[1,5]$ 中找数据 $5$，因此 $l=1,\ r=5$。由于 $l<r$，我们可以使用二分来查找。这样 $m=(l+r)/2=(1+5)/2=3$。
此时，$a[3]=5$，二分查找并没有完成，我们需要进一步缩小区域，看是否还有数据 $5$ 的存在。
根据二分的特性，$[4,5]$ 这个区间，肯定不会存在答案。答案只能在 $[1,3]$ 这个区间，注意 $a[3]$ 是可能的。
因此，我们使用 $m$ 的数据更新 $r$，即 $r=m$。也就是说，我们继续 $[l,r]$，即 $[1,3]$ 这个区间进行二分查找。

【步骤 $3$】

我们需要从 $[1,3]$ 中找数据 $5$，因此 $l=1,\ r=3$。由于 $l<r$，我们可以使用二分来查找。这样 $m=(l+r)/2=(1+3)/2=2$。
此时，$a[2]=5$，二分查找并没有完成，我们需要进一步缩小区域，看是否还有数据 $5$ 的存在。
根据二分的特性，$[3,3]$ 这个区间，肯定不会存在答案。答案只能在 $[1,2]$ 这个区间，注意 $a[2]$ 是可能的。
因此，我们使用 $m$ 的数据更新 $r$，即 $r=m$。也就是说，我们继续 $[l,r]$，即 $[1,2]$ 这个区间进行二分查找。

【步骤 $4$】

我们需要从 $[1,2]$ 中找数据 $5$，因此 $l=1,\ r=2$。由于 $l<r$，我们可以使用二分来查找。这样 $m=(l+r)/2=(1+2)/2=1$。
此时，$a[1]=1<5$，根据二分的特性，$[1,1]$ 这个区间，肯定不会存在答案。因此答案一定在 $[2,2]$ 这个区间。
因此，我们使用 $m+1$ 的数据更新 $l$，即 $l=m+1$。也就是说，我们继续 $[l,r]$，即 $[2,2]$ 这个区间进行二分查找。

【步骤 $5$】

我们需要从 $[2,2]$ 中找数据 $5$，因此 $l=2,\ r=2$。由于 $l<r$ 不成立，二分查找结束。
对应的答案为 $2$。也就是第一个数字 $5$ 出现在第 $2$ 个位置。

【伪代码】

如果 l<r 成立继续:
    更新 m=(l+r)/2
	以 a[m] 为界限判断条件是否成立
	如果 a[m]>=x，说明答案在区间 [l,m] 
	如果 a[m]<x，说明答案在区间 [m+1,r]
返回答案 l

【C++代码】

//在 [l,r] 中找第一个 x 的下标 
//>=x min  即大于等于 x 的最小值 
bool check1(LL m,LL x) {
	//以 a[m] 为界限判断二分是否成立
	return a[m]>=x;
	 
}
LL bsearch1(LL l, LL r, LL x) {
	while (l<r) {
		LL m=(l+r)/2;
		if (check1(m, x)) {
			r = m;
		} else {
			l = m+1;
		}
	}
	return l;
}