整数二分和小数二分

整数二分

20220108144457
20220108144656

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质,例如:arr[mid]>=x
else l = mid + 1;
}
return l;

//返回的l,是数组下标,对应结果的下标
//仅通过下标,无法判断找的对不对
//还需要进一步判断
int ans=bsearch_1(0,n-1);
if(arr[ans]==x) prinf("%d ",ans+1);//如果输出下标直接返回,如果是第几个位置还要下标+1
else printf("-1 ");
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}


P2249查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>

using namespace std;

const int N=1e6+10;

int arr[N];
int n,m;
int target;
int search(int l,int r)
{

while(l<r)
{
int mid=l+r>>1;
if(arr[mid]>=target) r=mid;
else l=mid+1;
}

return l;
}

int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%d",&arr[i]);
while(m--)
{
scanf("%d",&target);
int ans=search(0,n-1);
if(arr[ans]==target)
printf("%d ",ans+1);
else printf("-1 ");
}

return 0;
}


小数二分

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}