wordpress頁面屬性模板怎么添加泰安網(wǎng)站推廣優(yōu)化
整數(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ù)二分算法源代碼