二分查找Binary_Search

• 二分查找与二分答案
  
  • 笔记
    
    • 二分查找Binary_Search - 唔知叫咩emm - 博客园 (cnblogs.com)
      
    • Binary_Search_int.cpp
      
    • Binary_Search_double.cpp
      
  • 基础理论
    
    • 二分查找Binary Search（也称 折半搜索、对数搜索）
      
    • 应用场景，关键词
      
      • 在一个有序数组中查找某一元素的算法
        
      • 看见：排序+查找，就要想到二分查找
        
      • 找区间里面的一个值
        
        • 答案在区间里，就是二分答案，用二分来枚举答案
          
    • STL 的二分查找
      
      • 查找首个不小于给定值的元素的函数 std::lower_bound 和查找首个大于给定值的元素的函数 std::upper_bound，二者均定义于头文件 <algorithm> 中
        
      • 注意，不能用find()代替，find是顺序查找，不是二分查找，会TLE
        
    • 库函数的二分查找
      
      • bsearch 函数为 C 标准库实现的二分查找，定义在 <stdlib.h> 中。在 C++ 标准库里，该函数定义在 <cstdlib> 中。qsort 和 bsearch 是 C 语言中唯二的两个算法类函数。
        
      • 排序相关 STL - OI Wiki (oi-wiki.org)
        
    • 二分答案
      
      • 解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性，则满足使用二分法的条件。把这里的枚举换成二分，就变成了「二分答案」。
        
      • 我的理解：用二分的方法枚举答案
        
    • 三分
      
      • 未开始
        
        • P3382 【模板】三分法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
          
  • 文章
    
    • b站模板:二分查找为什么总是写错？_哔哩哔哩_bilibili
      
    • acwing
      
      • 常用代码模板1——基础算法 - AcWing
        
    • oi-wiki
      
      • 二分 - OI Wiki (oi-wiki.org)
        
  • 例题
    
    • 洛谷题集导图
      
      • 图中例题已全做完
        
    • 可直接用stl
      
      • P2249 【深基13.例1】查找 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        
        • 启蒙题
          
      • P1102 A-B 数对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        
    • 整数二分
      
      • P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        
        • 近乎模板题
          
      • P1182 数列分段 Section II - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        
        • 好题
          
        • 第一次几乎不会做
          
    • 浮点数二分
      
      • P1024 [NOIP2001 提高组] 一元三次方程求解 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
        
        • 暴力or二分
          
        • 第一次几乎不会做，这个知识点还不熟
          
        • 我提交的只是暴力，题解有二分正解，下次复习自己重新写正解
          
      • 69. x 的平方根 - 力扣（LeetCode）
        
 

/*Binary_Search_int.cpp*/
#include<bits/stdc++.h>
using namespace std;

/*
1、建模：划分蓝红区域，确定IsBlue()
2、确定返回l还是r
3、套用算法模板
4、(后处理...)
*/

//模板
bool check(int mid){// 检查mid是否满足某种性质
    return true;
}

int BinarySearch(int n){
    int l = -1;
    int r = n;
    int mid;
    while(l+1 != r){
        mid = r + (l-r)/2;  //防int溢出
        if (check(mid))l = mid;    //根据实际情况设计函数
        else r = mid;
    }
    return l; //根据实际情况返回l或者r
}

/*例子*/
vector<int> arr = {1,2,3,5,5,5,8,9};

int BinarySearch01(int x){
    int l = -1, r = arr.size(),mid;
    while(l+1 != r){
        mid = r + (l-r)/2;
        if(arr[mid]<x) l = mid;
        else r = mid;
    }
    return l;
}

int BinarySearch02(int x){
    int l = -1, r = arr.size(),mid;
    while(l+1 != r){
        mid = r + (l-r)/2;
        if(arr[mid]<x) l = mid;
        else r = mid;
    }
    return r;
}

int BinarySearch03(int x){
    int l = -1, r = arr.size(),mid;
    while(l+1 != r){
        mid = r + (l-r)/2;
        if(arr[mid]<=x) l = mid;
        else r = mid;
    }
    return l;
}

int BinarySearch04(int x){
    int l = -1, r = arr.size(),mid;
    while(l+1 != r){
        mid = r + (l-r)/2;
        if(arr[mid]<=x) l = mid;
        else r = mid;
    }
    return r;
}

int main(){
    cout<<BinarySearch01(5)<<endl;//找到最后一个<5的元素      输出2
    cout<<BinarySearch02(5)<<endl;//找到第一个>=5的元素       输出3
    cout<<BinarySearch03(5)<<endl;//找到最后一个<=5的元素     输出5
    cout<<BinarySearch04(5)<<endl;//找到第一个>5的元素        输出6
    return 0;
}

/*Binary_Search_double.cpp*/
#include<bits/stdc++.h>
using namespace std;

bool check(double x){// 检查x是否满足某种性质
} 
double bsearch_double(double l, double r){
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求(英文全称为epsilon，其来源为希腊字符ε的读音)
    while (r - l > eps){
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

int main(){

    return 0;
}