# 二分查找算法

## 整数的二分查找

``````bool check(int);

int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid))
r = mid;
else
l = mid + 1;
}
return l;
}

int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid))
l = mid;
else
r = mid - 1;
}
return l;
}
``````

## 示例

3次方根

c++:

``````#include <iostream>

using namespace std;

int main()
{
double n;
scanf("%lf", &n);
double l = -10000, r = 10000;
while (r - l >= 1e-8)
{
double mid = (l + r) / 2;
if (mid * mid * mid >= n)
r = mid;
else
l = mid;
}

printf("%f", l);
return 0;
}
``````

python:

``````n = float(input())
l, r = -10000, 10000.0

while r-l > 1e-12:
mid = (l+r)/2
if mid**3 >= n:
r = mid
else:
l = mid

print("%.6f" % (l))
``````

``````#include <iostream>

using namespace std;

const int N = 1000010;

int n, m;
int q[N];

int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
scanf("%d", &q[i]);
while (m--)
{
int x;

int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r >> 1;
if (x <= q[mid])
r = mid;
else
l = mid + 1;
}
if (q[l] != x)
cout << "-1 -1" << endl;
else
{
cout << l << " ";
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (x >= q[mid])
l = mid;
else
r = mid - 1;
}
cout << l << endl;
}
}
return 0;
}
``````

(0)
(0)