整數(shù)二分算法和浮點(diǎn)數(shù)二分算法

---

二分

現(xiàn)實(shí)中運(yùn)用到二分的就是猜數(shù)字的游戲 假如有A同學(xué)說B同學(xué)所說數(shù)的大小，B同學(xué)要在1~100中間猜中數(shù)字65，當(dāng)B同學(xué)每次說的數(shù)都是范圍的一半時(shí)這就算是一個(gè)二分查找的過程

二分查找的前提是這個(gè)數(shù)字序列要有單調(diào)性

基本步驟

初始化：

設(shè)定兩個(gè)指針，left 和 right，分別指向數(shù)組的起始和末尾。

計(jì)算中間位置：

使用公式 mid = left + (right - left) / 2 或者left+right>>1計(jì)算中間位置。

比較：

如果中間位置的元素等于目標(biāo)值，返回中間位置。
如果目標(biāo)值小于中間位置的元素，則將 right 更新為 mid - 1，繼續(xù)在左半部分查找。
如果目標(biāo)值大于中間位置的元素，則將 left 更新為 mid + 1，繼續(xù)在右半部分查找。

重復(fù)：

重復(fù)步驟 2 和 3，直到 left 超過 right。

結(jié)束：

如果在查找過程中未找到目標(biāo)值，返回一個(gè)表示未找到的結(jié)果（如 -1 或 None）。

二分查找算法的時(shí)間復(fù)雜度是 O(log n)，非常高效。

整數(shù)二分

二分的本質(zhì)并不是一定要單調(diào)，而是對一個(gè)區(qū)間可以化分成兩個(gè)部分，一部分一定滿足條件，另一部分一定不滿足，對于滿足這種條件的我們可以找出兩個(gè)邊界點(diǎn)，這樣的話二分算法可以尋找這個(gè)性質(zhì)的邊界（紅色和黑色的邊界都行，因?yàn)槭钦麛?shù)二分所以兩邊界不重合）。

第一種情況（二分左半部分）

假如說有一串?dāng)?shù)字1，2，3，3，4，4，5，6，8，8我們需要找到滿足小于等于3的最大情況的子序列，也就是我們需要找到最后一次出現(xiàn)的3，我們可以如何做呢？
我們讓一個(gè)mid=(l+r+1)/2 假如說a[mid]<=3,此時(shí)if(check(mid))==true說明此時(shí)mid指向的值可能是答案，但是我們無法保證其后面還有沒有答案是<=3的，所以此時(shí)應(yīng)該是l=mid,假如說此時(shí)a[mid]>=3,if(check(mid))==false說明此時(shí)mid指向的是一定不滿足條件的的那么此時(shí)應(yīng)該是r=mid-1。

我們繼續(xù)不段重復(fù)以上操作直到l>=r時(shí)退出循環(huán)。

第二種情況(二分右半部分)

還是這個(gè)數(shù)字序列這次我們要找1，2，3，3，4，4，5，6，8，8中第一次出現(xiàn)3的位置，我們應(yīng)該怎么做呢？
我們還是讓一個(gè)mid=(l+r)/2 假如說a[mid]>=3,此時(shí)if(check(mid))==true說明此時(shí)mid指向的值可能是答案，但是我們無法保證其前面還有沒有答案是>=3的，所以此時(shí)應(yīng)該是r=mid,假如說此時(shí)a[mid]<=3,if(check(mid))==false說明此時(shí)mid指向的是一定不滿足條件的的那么此時(shí)應(yīng)該是l=mid+1。

注意：第一種情況是（l+r+1）而不是（l+r）為為什么呢？

因?yàn)橛?jì)算機(jī)的除法都是向下取整的所以就會出現(xiàn)問題，假如說此時(shí)l=r-1那么mid=(l+r)/2=(l+l+1)/2=l然后我們假如發(fā)現(xiàn)l還是滿足條件的，那么此時(shí)就會陷入l=mid,mid=l的死循環(huán)

我們來寫一道題

洛谷P2249
下面的代碼是既有第一次出現(xiàn)，也有最后一次出現(xiàn)的，兩種情況都寫了。
代碼如下：

#include <iostream>
using namespace std;const int N = 1e5 + 10; // 定義數(shù)組的最大容量，數(shù)組a最多可以存放1e5個(gè)元素
int a[N], n, m; // 定義全局變量數(shù)組a，n為數(shù)組長度，m為查詢次數(shù)// check1函數(shù)用于檢查a[mid]是否大于等于目標(biāo)值x
bool check1(int mid, int x) {if (a[mid] >= x) {return true; // 如果a[mid]大于等于x，返回true，表示滿足條件} else {return false; // 否則返回false，表示不滿足條件}
}// check2函數(shù)用于檢查a[mid]是否小于等于目標(biāo)值x
bool check2(int mid, int x) {if (a[mid] <= x) {return true; // 如果a[mid]小于等于x，返回true，表示滿足條件} else {return false; // 否則返回false，表示不滿足條件}
}int main() {cin >> n >> m; // 輸入數(shù)組的長度n和查詢的次數(shù)mfor (int i = 1; i <= n; i++) {cin >> a[i]; // 依次輸入數(shù)組a的元素}while (m--) { // 對每一次查詢進(jìn)行處理，m次查詢int x; // 定義要查詢的目標(biāo)值xcin >> x; // 輸入目標(biāo)值x// 首先進(jìn)行二分查找，尋找第一個(gè)大于等于x的位置int l = 1, r = n; // 初始化左右邊界，l是左邊界，r是右邊界while (l < r) { // 當(dāng)左邊界小于右邊界時(shí)，繼續(xù)二分查找int mid = (l + r) >> 1; // 計(jì)算中間位置midif (check1(mid, x)) { // 如果a[mid]大于等于xr = mid; // 縮小右邊界至mid} else {l = mid + 1; // 否則縮小左邊界至mid+1}}// 查找完成后，檢查a[l]是否等于目標(biāo)值xif (a[l] == x) {cout << l << " "; // 如果a[l]等于x，輸出位置l} else {cout << -1 << " "; // 如果a[l]不等于x，輸出-1表示未找到}// 再進(jìn)行一次二分查找，尋找最后一個(gè)小于等于x的位置l = 1, r = n; // 重新初始化左右邊界while (l < r) {int mid = (l + r + 1) >> 1; // 計(jì)算中間位置mid，向上取整if (check2(mid, x)) { // 如果a[mid]小于等于xl = mid; // 縮小左邊界至mid} else {r = mid - 1; // 否則縮小右邊界至mid-1}}// 查找完成后，再次檢查a[l]是否等于目標(biāo)值xif (a[l] == x) {cout << l << " "; // 如果a[l]等于x，輸出找到的最后位置l} else {cout << -1 << " "; // 如果沒找到，輸出-1}cout<<endl;}
}

整數(shù)二分模板

bool check(int x) {// 這里是判斷x是否滿足某種性質(zhì)的函數(shù)，具體實(shí)現(xiàn)取決于實(shí)際問題// 可以根據(jù)x的值來返回true或false，用于二分查找中的判斷/* ... */
}// 區(qū)間[l, r]被劃分為[l, mid]和[mid + 1, r]時(shí)使用的二分查找
int bsearch_1(int l, int r) {// 二分查找的目的是在區(qū)間[l, r]中尋找滿足某種性質(zhì)的最小位置// l 是左邊界，r 是右邊界，最終返回滿足性質(zhì)的最小下標(biāo)while (l < r) { // 當(dāng)左邊界小于右邊界時(shí)，繼續(xù)進(jìn)行二分查找int mid = (l + r) >> 1; // 計(jì)算中間位置mid，使用右移操作進(jìn)行快速計(jì)算，相當(dāng)于 (l + r) / 2if (check(mid)) { // 如果check(mid)為true，表示mid滿足性質(zhì)r = mid; // 將右邊界縮小到mid，因?yàn)槲覀円覞M足性質(zhì)的最小位置} else { // 否則，mid不滿足性質(zhì)l = mid + 1; // 將左邊界縮小到mid + 1，因?yàn)閙id以及它左邊的值都不滿足條件}}return l; // 返回最終的左邊界，此時(shí)l == r，且為滿足性質(zhì)的最小位置
}// 區(qū)間[l, r]被劃分為[l, mid - 1]和[mid, r]時(shí)使用的二分查找
int bsearch_2(int l, int r) {// 二分查找的目的是在區(qū)間[l, r]中尋找滿足某種性質(zhì)的最大位置// l 是左邊界，r 是右邊界，最終返回滿足性質(zhì)的最大下標(biāo)while (l < r) { // 當(dāng)左邊界小于右邊界時(shí)，繼續(xù)進(jìn)行二分查找int mid = (l + r + 1) >> 1; // 計(jì)算中間位置mid，并向上取整，確保mid偏向右側(cè)if (check(mid)) { // 如果check(mid)為true，表示mid滿足性質(zhì)l = mid; // 將左邊界縮小到mid，因?yàn)槲覀円覞M足性質(zhì)的最大位置} else { // 否則，mid不滿足性質(zhì)r = mid - 1; // 將右邊界縮小到mid - 1，因?yàn)閙id以及它右邊的值都不滿足條件}}return l; // 返回最終的左邊界，此時(shí)l == r，且為滿足性質(zhì)的最大位置
}

浮點(diǎn)數(shù)二分算法

浮點(diǎn)數(shù)二分相較于整數(shù)二分更加簡單因?yàn)橹挥幸粋€(gè)模板，并且沒有邊界問題，浮點(diǎn)數(shù)的二分查找可以用于求解需要精確值的問題，例如求方程的解或幾何問題中涉及浮點(diǎn)精度的求解。與整數(shù)二分查找不同，浮點(diǎn)數(shù)二分查找必須考慮精度問題，因?yàn)楦↑c(diǎn)數(shù)無法精確到某個(gè)具體值，所以我們需要一個(gè)精度（如 epsilon），用于判斷二分查找的終止條件。

假如說我們需要找一個(gè)數(shù)x的平方等于目標(biāo)值2

代碼如下：

#include <iostream>
#include <cmath> // 包含abs函數(shù)，用于計(jì)算絕對值
using namespace std;// 定義一個(gè)需要使用二分法求解的函數(shù)，返回值為目標(biāo)函數(shù)值
double f(double x) {// 舉例：尋找函數(shù) f(x) = x^2 - 2 的根return x * x - 2;
}int main() {double l = 0, r = 2; // 初始區(qū)間[l, r]，假設(shè)根位于[0, 2]之間double eps = 1e-7;   // 定義精度eps，即當(dāng)結(jié)果誤差小于1e-7時(shí)停止迭代// 當(dāng)區(qū)間寬度大于精度要求時(shí)，繼續(xù)二分while (r - l > eps) {double mid = (l + r) / 2; // 計(jì)算中間值if (f(mid) > 0) { // 如果 f(mid) > 0，表示 mid 處的值在根的右側(cè)r = mid; // 縮小右邊界至mid} else { // 否則 f(mid) <= 0，表示 mid 處的值在根的左側(cè)或是根l = mid; // 縮小左邊界至mid}}// 輸出結(jié)果，l 和 r 最終都會逼近根cout << "x ≈ " << l << endl;cout << "驗(yàn)證結(jié)果: f(x) = " << f(l) << endl; // 輸出驗(yàn)證f(l)接近0
}

浮點(diǎn)數(shù)二分模板

// 函數(shù)原型：在浮點(diǎn)數(shù)區(qū)間 [l, r] 上使用二分查找，找到滿足某種性質(zhì)的浮點(diǎn)數(shù)
double bsearch_3(double l, double r)
{const double eps = 1e-6;   // eps 是精度控制的參數(shù)，當(dāng)區(qū)間長度小于 eps 時(shí)停止二分查找// 1e-6 表示小數(shù)點(diǎn)后 6 位精度，可根據(jù)題目要求調(diào)整精度// 當(dāng)區(qū)間長度大于 eps 時(shí)，繼續(xù)進(jìn)行二分查找while (r - l > eps){// 計(jì)算區(qū)間的中點(diǎn) middouble mid = (l + r) / 2;// 調(diào)用 check 函數(shù)判斷 mid 是否滿足給定的性質(zhì)// 假設(shè) check(mid) 返回 true，則意味著 mid 及其右側(cè)可能滿足性質(zhì)，// 因此將右區(qū)間收縮到 mid，繼續(xù)在左側(cè)區(qū)間 [l, mid] 上搜索if (check(mid)) r = mid;// 否則，mid 及其左側(cè)不滿足性質(zhì)，因此我們將左區(qū)間收縮到 mid，繼續(xù)在右側(cè)區(qū)間 [mid, r] 上搜索else l = mid;}// 最后返回左邊界 l（或右邊界 r），此時(shí)區(qū)間已經(jīng)很小，接近于精度要求的結(jié)果// 因?yàn)?l 和 r 的距離非常小，最終答案應(yīng)為 l 或 r 的近似值return l;
}

整數(shù)二分算法和浮點(diǎn)數(shù)二分算法源代碼