二分模板

整数二分算法模板

#include 
#include 
using namespace std;
int t, flag = 0;
int a[100];
int bisearch_1(int l , int r) { //返回数组中第一个大于或等与target的元素的下表
	while(l < r) {
		int mid = l+r >> 1;
		if(a[mid] >= t) r = mid;
		else l = mid + 1;
	}
	return l;
}
int bisearch_2(int l, int r) { //返回数组中最后一个小于target的元素的下标
	while(l < r) {
		int mid = l+r+1 >> 1;
		if(a[mid] <= t) l = mid;
		else r = mid - 1;
	}
	return l;
}
int main() {
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	cin >> t;
	int ans1 = bisearch_1(1, n);
	int ans2 = bisearch_2(1, n);
	int ans3 = lower_bound(a+1, a+n+1,t) - a;//返回数组中第一个大于等与target的元素的下标
	int ans4 = upper_bound(a+1, a+n+1,t) - a;//返回数组中第一个大于target的元素的下标
	cout << ans1 << endl;
	cout << ans2 << endl;
	cout << ans3 << endl;
	cout << ans4 << endl;
	return 0;
}

例1

5
1 3 3 3 5
3
2
4
2
5

例2

5
1 3 3 3 5
4
5
4
5
5

浮点数二分

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}