Binary Search
本文介绍了整数二分和浮点数二分，以及常用方法。
查找问题
一般实在给定序列中找到符合条件的元素的出现的位置。此类问题的最终的解往往是序列中的某个下标。
例 1 在长度为 10 的随机序列中找到第一个 3 出现的位置，没有则返回-1。
// E1
int a[10] , i; // 数组和下标变量
srand(6); // 设置随机种子
// 填充数组并且查看
for(i = 0 ; i <= 9 ; i++)
{
a[i] = rand() % 10;
cout << a[i] << " ";
}
cout << endl;
// 循序查找 找到输出下标
for(i = 0 ; i <= 9 ; i++)
{
if(a[i] == 3)
{
cout << i << endl;
break;
}
}
// 找不到输出-1
if(i == 10)
cout << -1;二分查找
原理 二分查找运用于有序序列中 将当前区间的中点元素和待查找元素比较 并且根据比较的结果来缩小区间。
这有点类似于猜数游戏。我在 [0 , 100] 之间选定了一个数 ?。第一次不妨猜 50 ，再 根据 50 和 ? 的大小关系来决定下一个猜的数是 25 还是 75。 按照此法最终找到 ?。
注意，我们找到 ? 不是 利用某个数和 ? 相等 来判别的，而是由某一时刻区间无法再缩小来确定的。如果 ? 就是 50 的话 区间会做如下变化
[0 , 100] , [0 , 50] , [25 , 50] , [37 , 50] , ........ [50 , 50] 来最终确定的。
整数二分查找的具体方法
在二分查找中 我会用过一个条件判断来将区间分为两个性质不同的段。
如在 节 2 中，根据和 ? 的大小关系 可以将区间分为。
或者
和 ? 的比较方法是在程序里确定的，且只会上图表现的两种中的一种。
在二分中有意义的结果点有两个，显然是下图中的 1 和 2点。
以此 我们介绍两种二分代码方法。
- 求得 左区间右端点(1 号点)的二分方法
int BinSearch_1(int l , int r)
{
while(l < r)
{
int mid = (l + r + 1) / 2;
if(check(mid)) l = mid;
else r = mid - 1;
}
return l;
}- 求得 右区间左端点的(2 号点)的二分方法
int BinSearch_2(int l , int r)
{
while(l < r)
{
int mid = (l + r) / 2;
if(check(mid)) r = mid ;
else l = mid + 1;
}
return l;
}方法理论
上下中点
观察两种方法中求取中点的不同写法。
int mid = (l + r) / 2;int mid = (l + r + 1) / 2;对于奇数区间，两式求得的位置是一样的。
对于偶数区间，两式分别求得上下中点。
答案
特化一下答案所在的区间。
不难看出，1 号点在左区间中为上中点，2 号点在右区间为下中点。
可出这些原则可以记忆对应的代码:
- 明确所求的点，写对应的取中点方法
- 写
checkmid()时让答案点保持在其区间内- 求 1 号点就检查 答案 是否在左区间，反之同理
- 移动区间端点
- 保持答案在区间内
- 保证区间每次都至少减少 1
一个整数二分的实际问题
- 描述 有一个升序排序的数组
{1 , 2 , 2 , 3 , 3 , 4}。 - 用户给出查询 q 输出 q 在数组中出现的起始位置和结束位置。
- 如果数组中没有 q 则输出
-1 -1。
int a[] = {1 , 2 , 2 , 3 , 3 , 4};
int q;
cin >> q;对于第一个 q 使用节 3 求 2 号点的方法
int l = 0 , r = sizeof(a) / sizeof(int) - 1; // 二分的起始区间 0 - 数组的最后一个下标
while(l < r)
{
int mid = (l + r) / 2;
if(a[mid] >= q) r = mid; // 写目标q(蓝色)所在那部分 即 >= q
else l = mid + 1;
}
if(a[l] != q)
cout << "-1 -1" << endl;对于第二个 q 使用节 3 求 1 号点的方法
else
{
cout << l << " ";
// 对于最后一个q 依据上法可以分为这样两个区间
// <=q 和 >q 此时要寻找左区间的左端点
l = 0 , r = sizeof(a) / sizeof(int) - 1;
while(l < r)
{
int mid = (l + r + 1) / 2;
if(a[mid] <= q) l = mid; // 写目标q(红色)所在的区间 即 <= q
else r = mid - 1;
}
cout << l << " ";
}5.浮点数二分
- 一个例题
// 使用浮点数二分求0.01的平方根
void Exe1()
{
double l = 0 , r = 1;
while(r - l > 1e-7) // 区别于整数 这里只要左右端点 "足够接近" 即可
{
double mid = (l + r) / 2;
// 这里直接调整左右端点 没有+1的问题
if(mid * mid >= 0.01) r = mid;
else l = mid;
}
cout << l;
}版权所有
版权归属：