# 【算法】二分查找（整数二分和浮点数二分）

（不清楚怎么算时间复杂度的小伙伴可以看看这篇文章哦~https://blog.csdn.net/m0_62531913/article/details/132019833?spm=1001.2014.3001.5502）

# 2. 整数二分模板

int find(int x)
{

int l = 0, r = n + 1; //开区间
while (l + 1 < r)  //l+1==r时结束
{

int mid = (l + r) >> 1;  //相当于mid=(l+r)/2;
if (a[mid] <= x) l = mid;
else r = mid;
}
return l;
}


int find(int x)
{

int l = 0, r = n + 1; //开区间
while (l + 1 < r)  //l+1==r时结束
{

int mid = (l + r) >> 1;  //相当于mid=(l+r)/2;
if (a[mid] >= x) r = mid;
else l = mid;
}
return r;
}


# 3. 整数二分模板题

## 3.1 洛谷 P2249 【深基13.例1】查找

#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. 数的范围

#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. 浮点数二分

（其实是个二分答案的题目）

y=x^3，我们知道这是个单调递增的函数。

-10000开三次方根大概是-27，10000开三次方根大概是27。

# 5. 浮点数二分模板

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. 浮点数二分模板题

## 6.1 Acwing 790.数的三次方根

#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 提高组] 一元三次方程求解

（1）若f(l)==0，l为方程的根。

（2）若f(l)*f(r)<0，则根在区间[l，r]内。

（3）若f(l)*f(r)>0，则根不在区间[l，r]内。设定[r，r+1]为下一搜索区间。

#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++)  //枚举每一个可能的根
{

double l = i, r = i + 1;
if (f(l) == 0) printf("%.2lf ", i); //左端点是根，直接输出
if (f(l) * f(r) < 0)  //根在区间[l,r]中
{

while (r - l > 1e-4)  //浮点数二分
{

double mid = (l + r) / 2;  //计算区间[l，r]的中间位置
if (f(l) * f(mid) < 0) r = mid;  //若根在左子区间，则调整右端点
else l = mid;  //若根在右子区间，则调整左端点
}
printf("%.2lf ", l);
}
}
return 0;
}


# 7. 总结

|
30天前
|

【算法】二分查找——二分查找
【算法】二分查找——二分查找
18 0
|
30天前
|

【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
44 0
|
15天前
|

17 2
|
28天前
|

23 0
|
3月前
|

38 3
|
3月前
|

**顺序查找时间复杂度为O(n)**，适合无序列表，可以通过enumerate或直接遍历索引来实现。**二分查找时间复杂度为O(logn)**，适用于有序列表，利用Python中left、right指针和mid点不断缩小搜索范围。效率上二分查找更优。
25 2
|
2月前
|

JS 【算法】二分查找
JS 【算法】二分查找
23 0
|
3月前
|

22 0
|
7天前
|

38 20
|
7天前
|

40 19