二分查找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;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/525943.html

標籤：其他

上一篇：Codeforces 1666 I. Interactive Treasure Hunt