码农知识堂 - 1000bd
  •   Python
  •   PHP
  •   JS/TS
  •   JAVA
  •   C/C++
  •   C#
  •   GO
  •   Kotlin
  •   Swift
  • 基础二分学习笔记


    模板 : 

     个人倾向第一种 ;

     

     

     

     整数二分 : 

    最大化查找 :

    可行区域在左侧 : 查找最后一个<=q的数的下标 : 

    1. int find(int q){// 查找最后一个 <= q 的下标
    2. int l = 0 , r = n + 1 ;
    3. while(l + 1 < r){
    4. int mid = l + r >> 1 ;
    5. if(a[mid]<=q) l = mid ;
    6. else r = mid ;
    7. }
    8. return l ;
    9. }

     最小化查找 : 

    可行区域在右侧 : 查找第一个>=q的数的下标 :
     

    1. int find(int q){ // 查找第一个>=q的下标
    2. int l = 0 , r = n + 1 ;
    3. while(l + 1 < r){
    4. int mid = l + r >> 1 ;
    5. if(a[mid]>=q) r = mid ;
    6. else l = mid ;
    7. }
    8. return r;
    9. }

    浮点数二分 : 

    1. double find(double l, double r){
    2. const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求
    3. while (r - l > eps)
    4. {
    5. double mid = (l + r) / 2;
    6. if (check(mid)) r = mid;
    7. else l = mid;
    8. }
    9. return l;
    10. }

    以求一个浮点数(-10000 <= y <= 10000) 的三次方根 为例:

    1. double find(double y){ // 最大化查找
    2. double l = -100 , r = 100 ;
    3. while(r-l>1e-5){
    4. double mid = (l + r) / 2 ;
    5. if(mid * mid * mid <= y) l = mid;
    6. else r = mid ;
    7. }
    8. return l ;
    9. }

    例题 : 

    35 . 搜索插入位置

    . - 力扣(LeetCode)

    最小化查找 : 

    1. class Solution {
    2. public:
    3. int searchInsert(vector<int>& nums, int target) {
    4. // 第一个 >= target 的下标
    5. int n = nums.size() ;
    6. int l = -1 , r = n ;
    7. while(l + 1 < r){// l + 1 == n 结束
    8. int mid = l + r >> 1 ;
    9. if(nums[mid]>=target) r = mid ;
    10. else l = mid ;
    11. }
    12. // nums[r] ;
    13. return r ;
    14. }
    15. };

    P2249 【深基13.例1】查找

    【深基13.例1】查找 - 洛谷

    最小化查找 : 

    1. #include
    2. using namespace std ;
    3. const int N = 1e6 + 10 ;
    4. int a[N] ;
    5. int main(){
    6. int n , m ; cin >> n >> m ;
    7. for(int i=1;i<=n;i++) cin >> a[i] ;
    8. while(m--){
    9. int q ; cin >> q ;
    10. int l = 0 , r = n + 1 ;
    11. while(l + 1 < r){
    12. int mid = l + r >> 1 ;
    13. if(a[mid] >= q) r = mid ;
    14. else l = mid ;
    15. }
    16. if(a[r]==q) cout << r << " " ;
    17. else cout << -1 << " " ;
    18. }
    19. }

    P1024 [NOIP2001 提高组] 一元三次方程求解

    [NOIP2001 提高组] 一元三次方程求解 - 洛谷

    浮点数二分 : 

    1. #include
    2. using namespace std ;
    3. const int N = 1e6 + 10 ;
    4. double a , b , c , d ;
    5. double f(double x){
    6. return a * x * x * x + b * x * x + c * x + d ;
    7. }
    8. double find(double l , double r){
    9. while(r-l>0.0001){
    10. double mid = (l + r) / 2 ;
    11. if(f(mid) * f(r) < 0) l = mid ;
    12. else r = mid ;
    13. }
    14. return l ;
    15. }
    16. int main(){
    17. cin >> a >> b >> c >> d ;
    18. for(int i=-100;i<100;i++){
    19. double y1 = f(i) , y2 = f(i + 1) ;
    20. if(!y1) printf("%.2f ",1.0 * i) ;
    21. if(y1 * y2 < 0){
    22. printf("%.2f " , find(i , i + 1)) ;
    23. }
    24. }
    25. }

    学习视频地址 : 

    A05 二分查找算法 最好的板子_哔哩哔哩_bilibili

  • 相关阅读:
    Nginx解析漏洞
    【iOS】——分类、扩展和关联对象
    Biotin-HPDP(129179-83-5),一个巯基反应性的生物素化试剂
    GD32单片机远程升级下载,手机在线升级下载程序,GD32在线固件下载升级,手机下载程序固件方法
    vueRouter个人笔记
    传统广电媒体为何选择上云?有何优势?
    思考如何完成一个审批流
    黄金投资新手指南:投资现货黄金怎样开户?
    C#编程题分享(1)
    你的新进程是如何被内核调度执行到的?(下)
  • 原文地址:https://blog.csdn.net/ros275229/article/details/136424506
  • 最新文章
  • 攻防演习之三天拿下官网站群
    数据安全治理学习——前期安全规划和安全管理体系建设
    企业安全 | 企业内一次钓鱼演练准备过程
    内网渗透测试 | Kerberos协议及其部分攻击手法
    0day的产生 | 不懂代码的"代码审计"
    安装scrcpy-client模块av模块异常,环境问题解决方案
    leetcode hot100【LeetCode 279. 完全平方数】java实现
    OpenWrt下安装Mosquitto
    AnatoMask论文汇总
    【AI日记】24.11.01 LangChain、openai api和github copilot
  • 热门文章
  • 十款代码表白小特效 一个比一个浪漫 赶紧收藏起来吧!!!
    奉劝各位学弟学妹们,该打造你的技术影响力了!
    五年了,我在 CSDN 的两个一百万。
    Java俄罗斯方块,老程序员花了一个周末,连接中学年代!
    面试官都震惊,你这网络基础可以啊!
    你真的会用百度吗?我不信 — 那些不为人知的搜索引擎语法
    心情不好的时候,用 Python 画棵樱花树送给自己吧
    通宵一晚做出来的一款类似CS的第一人称射击游戏Demo!原来做游戏也不是很难,连憨憨学妹都学会了!
    13 万字 C 语言从入门到精通保姆级教程2021 年版
    10行代码集2000张美女图,Python爬虫120例,再上征途
Copyright © 2022 侵权请联系2656653265@qq.com    京ICP备2022015340号-1
正则表达式工具 cron表达式工具 密码生成工具

京公网安备 11010502049817号