深入分析一下二分算法

二分算法的应用大体分为两种,即整数二分与浮点数二分,整数二分可分为二分查找,左侧边界查找与右侧边界查找三种情况。

 

整数二分

 

一.二分查找

应用场景为在一个有序数组中查找一个数的位置,时间复杂度为logn。

代码如下:

int binarysearch(int a[],int t)
{
    int l=0,r=a.length()-1;
    while (r >= l)
    {
        int mid = l + r >> 1;
        if (a[mid] == t)
            return mid;
        else if (a[mid] > t) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
    
}

1.为什么是r>=l而不是r>l

从l和r的初始化可以看出,该二分算法的每次查找的范围都是闭区间,即[l,r],所以如果while的终止条件为r>l,r=l=2时,此时的查找范围为[2,2],while循环结束,2是没有被查找的,所以应设置为r>=l.

2.为什么r=mid-1,l=mid+1

mid每次把[l,r]区间划分为[l,mid-1],mid,[mid+1,r],a[mid]是不需要进行下一次二分搜索的,所以r=mid-1或l=mid+1.

 

二.寻找左侧边界的二分搜索

应用场景在一个有序数组中多个重复数,例如:1,3,5,5,5,7,7,这个数组,目标为5,该算法输出第一个5所在的位置,即5这个字串左边界的位置

代码如下:

#include<iostream>
using namespace std;
const int N = 10010;
int a[N];
int n,t;
int left_binarysearch(int a[], int t)
{
    int l = 0, r = n;
    while (r > l)
    {
        int mid = l + r >> 1;
        if (a[mid] == t)
            r = mid;
        else if (a[mid] > t) r = mid;
        else l = mid + 1;
    }
    if (a[l] == t) return l;
    else return -1;

}
int main()
{
	cin >> n>>t;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	cout<<left_binarysearch(a,t);
	return 0;
}

1.为什么这里是r>l

在这里我的r=n,所以我的查找区间为[l.r)的左闭右开区间,当r=l=2是[2,2)为空区间,是可以终止while循环的

2.为什么r=mid而l=mid+1

因为查找区间为左闭右开区间,当刷新查找左边界时,如果l=mid则会让mid进入下一次查找范围,但mid是不需要进入下一次查找范围的,所以l=mid+1;刷新右边界时,r=mid为开区间,即下次查找范围是[l,mid),这个范围不包含mid,所以r=mid

 

三.寻找右侧边界的二分查找

应用场景与寻找左侧边界二分查找的应用场景相同。

#include<iostream>
using namespace std;
const int N = 10010;
int a[N];
int n,t;
int right_binarysearch(int a[], int t)
{
    int l= 0, r = n;

    while (l < r) {
        int mid = l + r >> 1;
        if (a[mid] == t) {
           l = mid + 1; // 注意
        }
        else if (a[mid] < t) {
          l = mid + 1;
        }
        else if (a[mid] > t) {
            r = mid;
        }
    }
    if (a[l - 1] == t) return l - 1;//注意
    else return -1;

}
int main()
{
    cin >> n>>t;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    cout<<right_binarysearch(a,t);
    return 0;
}

重点讲一下两个注意,这两处也是左边界和右边界的唯二区别。

第一处注意:由于我要寻找的是右边界,应该寻找一串相同数字中最后一个的位置,所以查找范围应该刷新为[mid+1,r)

第二处注意:由于我等于t是left刷新为mid+1,如果我的mid此时就是我的右边界,那么刷新之后我的a[l[是不等于t的,而a[l-1]才是等于t的最后一个数,

感觉自己讲的有点抽象,下面是一个寻找右边界例子的演示:

深入分析一下二分算法

 

 

从代码的记忆角度来说,整数二分查找可单独记忆,左右边界的查找放一起记忆,并且使用样例来检验是否记忆正确。

 

浮点数二分

最经典的例题就是数的三次方根

题目链接:https://www.acwing.com/activity/content/problem/content/824/

 

AC代码如下:

#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
    void isearch(double);
    double x;
    cin>>x;
    isearch(x);
    return 0;
}
void isearch(double x)
{
    double m,l;
    m=10000;
    l=-10000;
    for(int i=0;i<100;i++)
    {
        double mid=(l+m)/2;
        if(mid*mid*mid>=x) m=mid;
        else l=mid;
    }
    cout<<fixed<<setprecision(6)<<l;
}

严格二分即可,唯一注意一下循环的写法,也可以写成while(r-l>1e-8).

 

上一篇:CMAKE编译ORB-SLAM2时,报错找不到Eigen3,报错Eigen3 found!之类错误(已解决)


下一篇:if else流程判断语句(1)之 从入门到放弃的第1天