大家好！今天我們來學(xué)習(xí)二分查找算法，這是一種效率很高的算法哦！
目錄
1. 整數(shù)二分
2. 整數(shù)二分模板
3. 整數(shù)二分模板題
3.1 洛谷 P2249 【深基13.例1】查找
3.2?Acwing789. 數(shù)的范圍
4. 浮點(diǎn)數(shù)二分
5. 浮點(diǎn)數(shù)二分模板
6. 浮點(diǎn)數(shù)二分模板題
6.1 Acwing 790.數(shù)的三次方根
6.2 洛谷 P1024 [NOIP2001 提高組] 一元三次方程求解
7. 總結(jié)
二分查找也稱折半查找（Binary Search），是一種效率較高的查找方法，時(shí)間復(fù)雜度為O(logN)。
（不清楚怎么算時(shí)間復(fù)雜度的小伙伴可以看看這篇文章哦~https://blog.csdn.net/m0_62531913/article/details/132019833?spm=1001.2014.3001.5502）
二分查找采用了“分治”策略。使用二分查找時(shí)，數(shù)組中的元素之間得有單調(diào)性（升序或者降序）。
二分的模板據(jù)我目前所知有三個(gè)，但是下面是我個(gè)人認(rèn)為最好的一種（比較簡單，不容易寫錯(cuò)~）
1. 整數(shù)二分
整數(shù)二分過程：
?普遍規(guī)律：
?我們發(fā)現(xiàn)：
2. 整數(shù)二分模板
查找最后一個(gè)<=x的數(shù)的下標(biāo)：
int find(int x)
{
int l = 0, r = n + 1; //開區(qū)間
while (l + 1 < r) //l+1==r時(shí)結(jié)束
{
int mid = (l + r) >> 1; //相當(dāng)于mid=(l+r)/2;
if (a[mid] <= x) l = mid;
else r = mid;
}
return l;
}查找第一個(gè)>=x的數(shù)的下標(biāo)：
int find(int x)
{
int l = 0, r = n + 1; //開區(qū)間
while (l + 1 < r) //l+1==r時(shí)結(jié)束
{
int mid = (l + r) >> 1; //相當(dāng)于mid=(l+r)/2;
if (a[mid] >= x) r = mid;
else l = mid;
}
return r;
}3. 整數(shù)二分模板題
3.1 洛谷 P2249 【深基13.例1】查找
原題鏈接：https://www.luogu.com.cn/problem/P2249
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], n, m;
int find(int x)
{
int l = 0, r = n + 1;
while (l + 1 < r)
{
int mid = (l + r) >> 1;
if (a[mid] >= x) r = mid;
else l = mid;
}
if (a[r] == x) return r;
else return -1;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
while (m--)
{
int k;
scanf("%d", &k);
printf("%d ", find(k));
}
return 0;
}
3.2?Acwing789. 數(shù)的范圍
原題鏈接：https://www.acwing.com/problem/content/791/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], n, q;
int find1(int x)
{
int l = -1, r = n;
while (l + 1 < r)
{
int mid = (l + r) >> 1;
if (a[mid] >= x) r = mid;
else l = mid;
}
if (a[r] == x) return r;
else return -1;
}
int find2(int x)
{
int l = -1, r = n;
while (l + 1 < r)
{
int mid = (l + r) >> 1;
if (a[mid] <= x) l = mid;
else r = mid;
}
if (a[l] == x) return l;
else return -1;
}
int main()
{
scanf("%d%d", &n, &q);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
while (q--)
{
int k;
scanf("%d", &k);
printf("%d %d\n", find1(k), find2(k));
}
}
4. 浮點(diǎn)數(shù)二分
我們看下圖：
分析：
（其實(shí)是個(gè)二分答案的題目）
y=x^3，我們知道這是個(gè)單調(diào)遞增的函數(shù)。
-10000開三次方根大概是-27，10000開三次方根大概是27。
因?yàn)?10000<=y<=10000，我們?yōu)榱朔奖?，把左邊界設(shè)置成-100，右邊界設(shè)置成100。
?我們可以直觀看到-27~27包含在-100~100。所以這樣設(shè)置左右邊界是沒有問題滴。
我們不斷二分縮小范圍，當(dāng)l和r非常接近時(shí)（r-l<=1e-8）,我們就認(rèn)為找到了這個(gè)三次方根。
否則我們用while(r-l>=1e-8)繼續(xù)循環(huán)遍歷。
又因?yàn)槭沁f增的，所以mid*mid*mid<=y，我們讓區(qū)間往右靠（l=mid）；反之，當(dāng)mid*mid*mid>y時(shí)，我們讓區(qū)間往左靠（r=mid）。
最后返回左邊界l即可。（其實(shí)這里返回左邊界l和右邊界r都可以，因?yàn)樗鼈兎浅７浅７浅＝咏?/p>
5. 浮點(diǎn)數(shù)二分模板
double find(double y)
{
double l = -100, r = 100;
while (r - l > 1e-8)
{
double mid = (l + r) / 2;
if (mid * mid * mid <= y) l = mid;
else r = mid;
}
return l;
}6. 浮點(diǎn)數(shù)二分模板題
6.1 Acwing 790.數(shù)的三次方根
原題鏈接：https://www.acwing.com/problem/content/792/
#include<bits/stdc++.h>
using namespace std;
double n;
int main()
{
scanf("%lf", &n);
double l = -100, r = 100;
while (r - l > 1e-8)
{
double mid = (l + r) / 2;
if (mid * mid * mid <= n) l = mid;
else r = mid;
}
printf("%.6lf\n", l);
return 0;
}
6.2 洛谷 P1024 [NOIP2001 提高組] 一元三次方程求解
原題鏈接：https://www.luogu.com.cn/problem/P1024
?思路分析：
因?yàn)橛腥齻€(gè)不同實(shí)根x，且根x的區(qū)間為-100到100，根與根之差的絕對值>=1。
我們就可以從根x的區(qū)間[-100,100]進(jìn)行枚舉，我們將搜索區(qū)間定為[l，r]，而r=l+1。
根據(jù)題目提示（即零點(diǎn)定理），我們知道：
（1）若f(l)==0，l為方程的根。
（2）若f(l)*f(r)<0，則根在區(qū)間[l，r]內(nèi)。
（3）若f(l)*f(r)>0，則根不在區(qū)間[l，r]內(nèi)。設(shè)定[r，r+1]為下一搜索區(qū)間。
當(dāng)遇到情況（2）時(shí)，我們要想知道根的確切位置，就可以進(jìn)行二分（因?yàn)楦菍?shí)數(shù)，所以我們采用浮點(diǎn)數(shù)二分）
二分，設(shè)區(qū)間中間位置為mid，mid=(l+r)/2。將區(qū)間[l，r]分為左右兩個(gè)區(qū)間，左子區(qū)間[l，mid]和右子區(qū)間[mid，r]。
若f(l)*f(mid)<0（根在左子區(qū)間），我們調(diào)整右端點(diǎn)繼續(xù)二分（r=mid）。
若f(mid)*f(r)<0（根在右子區(qū)間），我們調(diào)整左端點(diǎn)繼續(xù)二分（l=mid）。
一直到找到根時(shí)停止循環(huán)，此時(shí)l就是方程的根。（因?yàn)?strong>精度足夠，所以這里也可以讓r作為方程的根）
#include<bits/stdc++.h>
using namespace std;
double a, b, c, d;
double f(double x)
{
return a * x * x * x + b * x * x + c * x + d;
}
int main()
{
scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
for (double i = -100; i <= 100; i++) //枚舉每一個(gè)可能的根
{
double l = i, r = i + 1;
if (f(l) == 0) printf("%.2lf ", i); //左端點(diǎn)是根，直接輸出
if (f(l) * f(r) < 0) //根在區(qū)間[l,r]中
{
while (r - l > 1e-4) //浮點(diǎn)數(shù)二分
{
double mid = (l + r) / 2; //計(jì)算區(qū)間[l，r]的中間位置
if (f(l) * f(mid) < 0) r = mid; //若根在左子區(qū)間，則調(diào)整右端點(diǎn)
else l = mid; //若根在右子區(qū)間，則調(diào)整左端點(diǎn)
}
printf("%.2lf ", l);
}
}
return 0;
}
文章來源：http://www.zghlxwxcb.cn/news/detail-687128.html
7. 總結(jié)
二分查找體現(xiàn)了“分治”的思想，又是二分答案的基礎(chǔ)，效率又非常高（O(logN)），所以我們學(xué)好這個(gè)算法很有必要哦！文章來源地址http://www.zghlxwxcb.cn/news/detail-687128.html
到了這里，關(guān)于【算法】二分查找（整數(shù)二分和浮點(diǎn)數(shù)二分）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
