IT评测·应用市场-qidao123.com技术社区

标题: 算法：二分讲解 [打印本页]

---

作者: 欢乐狗    时间: 2024-10-29 00:22
标题: 算法：二分讲解
二分的基本认识：

1. #include<bits/stdc++.h>
2. using namespace std;
3. //二分法 有序的序列找东西  left  right
4. /*
5. 1~100的数字
6. mid=(left+right)/2;
7. right=mid-1;
8. left=mid+1;
9. while(left<=right)
11. while(left<=right){
12.         mid=(left+right)/2
13.         if(mid==ans) return 0;
14.         else if(mid>ans) right=mid-1;
15.         else if(mid<ans) left=mid+1;
16. }
17. 1.二分数字  2.二分数组下标
18. 2.小数二分
19. */
20. double a;
21. int main(){
22.         cin>>a;
23.         double l=0,r=a,mid;
24.         while(r-l>=0.0001){ //l<=r  r-l>=0 整数的
25.                 mid=(l+r)/2;
26.                 if(mid*mid==a){
27.                         printf("%.3lf",mid);
28.                         return 0;
29.                 }else if(mid*mid>a){
30.                         r=mid; //不进行  r=mid-0.0001;
31.                 }else{
32.                         l=mid;
33.                 }
34.         }
35.         printf("%.3lf %.3lf",l,r);
37.         return 0;
38. }

复制代码

1. #include<iostream>
2. #include<cstdio>
3. using namespace std;
4. //二分的停止为 left<=right   
5. //每次要获取一个 mid=(left+right)/2
6. //小了  变left = mid + 1 
7. //大了  变right= mid - 1 
8. int k;     
9. int main(){
10.     cin>>k;
11.     //要求猜的数字就是k
12.     //left right 是用于确定猜数字的范围
13.     int left=1,right=100,mid,cnt=0;
14.     while(left<=right){
15.         //获取一个中间值
16.         mid=(left+right)/2;
17.         cnt++;//次数增加 
18.         //判断大了还是小了
19.         if(mid>k){ //大了 
20.             right=mid-1; 
21.         } else if(mid<k){
22.             left=mid+1;
23.         }else{ //等于 
24.             cout<<cnt;
25.             return 0;
26.         }
27.     } 
29.     return 0;
30. }

复制代码

 二分基础练习：

(1)二分正常练习

(1)AC题解：

1. #include<bits/stdc++.h>
2. using namespace std;
3. int ans,n,a[10005]; 
4. int main(){
5.     cin>>n;
6.     for(int i=1;i<=n;i++) cin>>a[i];
7.     cin>>ans;
8.     int left=1,right=n,mid;
9.     while(right>=left){
10.         mid=(left+right)/2; //下标 
11.         if(a[mid]>ans){
12.             right=mid-1;
13.         }else if(a[mid]<ans){
14.             left=mid+1;
15.         }else{
16.             cout<<mid; //答案下标 
17.             return 0;
18.         }
19.     }
20.     cout<<-1；
21.     return 0;
22. }

复制代码

 (2) 标题：

1. 要求输入一个整数
2. 求这个整数开立方根的结果保留5位小数
3. 例如：
4. 输入：27
5. 输出：3.00000
6. 输入：5
7. 输出：1.70998

复制代码

（2）AC题解：

1. #include<bits/stdc++.h>
2. using namespace std;
3. double n;
4. int main(){
5.         cin>>n;
6.         double left=0,right=n,mid;
7.         while(right-left>=0.0000001){
8.                 mid=(right+left)/2;
9.                 if(mid*mid*mid>n){
10.                         right=mid;
11.                 }else if(mid*mid*mid<n){
12.                         left=mid;
13.                 }else{
14.                         printf("%.5lf",mid);
15.                         return 0;
16.                 }
17.         }
18.         printf("%.5lf",mid);
19.         return 0;
20. }

复制代码

（3）练习题

（3）AC题解：

1. #include<iostream>
2. #include<cstdio>
3. using namespace std;
4. int a[1000005],n,m,x;
5. int main(){
6.         cin>>n>>m;
7.         for(int i=1;i<=n;i++) cin>>a[i];
8.         for(int i=1;i<=m;i++){
9.                 cin>>x;//x就是要查找的数据
10.                 int left=1,right=n,mid,ans=-1;
11.                 while(left<=right){
12. //                        mid=(right+left)/2;
13.                         mid=(right-left)/2+left;
14.                         if(a[mid]>=x){ //a[mid] 还要继续缩短范围
15.                                 right=mid-1;
16.                         }else{
17.                                 left=mid+1;
18.                         }
19.                         if(a[left]==x){ //真正的答案是放在最左边的
20.                                 ans=left;
21.                                 break;
22.                         }
23.                 }
24.                 cout<<ans<<" ";
25.         }
26.         return 0;
27. }

复制代码

（4）练习题

（4）AC题解：

1. #include<bits/stdc++.h>
2. using namespace std;
3. long long a[200005],n,c,ans;
4. int main(){
5.         cin>>n>>c;
6.         for(int i=1;i<=n;i++) cin>>a[i];
7.         sort(a+1,a+n+1);
8.         for(int i=1;i<=n;i++){
9.                 long long A=c+a[i];//要查找的内容
10.                 int ansl,ansr;
11.                 //是A的最左边的
12.                 int left=1,right=n,mid;//下标
13.                 while(left<=right){
14.                         mid=(left+right)/2;
15.                         if(a[mid]>=A) right=mid-1;
16.                         else left=mid+1;
17.                 }
18.                 ansl=left;
19.                 //是A的最右边的
20.                 left=1,right=n;//下标
21.                 while(left<=right){
22.                         mid=(left+right)/2;
23.                         if(a[mid]>A) right=mid-1;
24.                         else left=mid+1;
25.                 }
26.                 ansr=right;
27.                 ans+=ansr-ansl+1;
28.         }
29.         cout<<ans;
30.         return 0;
31. }

复制代码

拓展 ：

lower_bound()和upper_bound().

1. #include<iostream>
2. #include<cstdio>
3. #include<algorithm>
4. using namespace std;
5. /*
6. lower_bound() //第一个不小于查找的元素的下标
7. upper_bound() //第一个大于查找元素的下标
8. */
9. int a[12]={1,3,3,3,5,7,9,11,13,15,15};
10. int main(){
11.         //1,3, 6 sort(a+1,a+n+1)
12.         cout<<lower_bound(a,a+11,6)-a<<endl; //logn
13.         cout<<upper_bound(a,a+11,3)-a<<endl;
14.         if(a[lower_bound(a,a+11,6)-a]==ans) cout<<lower_bound(a,a+11,6)-a;
15.         else cout<<-1;
16.         return 0;
17. }

复制代码

小数的二分 ：

1. #include<iostream>
2. #include<cstdio>
3. using namespace std;
4. //小数二分的特点 误差  精确值 我们需要通过精确值来写循环的判断
5. double k;
6. int main(){
7.         cin>>k;
8.         double left=0,right=k,mid;
9.         while(right-left>=0.0001){ //0.0001 是因为精确值是0.001  
10.                 mid=(right+left)/2;
11.                 if(mid*mid>k){
12.                         right=mid;
13.                 }else if(mid*mid<k){
14.                         left=mid;
15.                 }else{
16. //                        cout<<mid; //用于整数
17.                         printf("%.3lf",mid);
18.                         return 0;
19.                 }
20.         }
21.         printf("%.3lf",mid);
22. //        cout<<mid;
23.         return 0;
24. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4