|
二分查找是我们学习算法时非常常见的一种查找算法，这种每次折半的方式相对于暴力枚举，时间复杂度得到了极大的降低，是一种非常有用的小算法。本文主要讲解笔者在学习二分算法中理解。
一，最朴素的二分如下所示
void binary_search()
{
int l=0,r=n;//要搜索的数组长度为n
while(r>l)
{
int mid=(l+r)/2;
if(num[mid]==k)//当查询到了你要找的数k
{
return true;//返回值为真
}
else if(num[mid]<k)
{
l=mid;
}
else
{
r=mid;
}
return false;//找不到则返回值为假
}
但是在实际应用中，这种写法往往会存在多种问题
1.r与l过大导致超出数据限制
int mid=(l+r)/2;//若l和r过大，则会存在两数相加超出数据限制的情况
int mid=l+(r-l)/2;//改成这种写法，则会避免两个大数直接相加
2.出现死循环
if(num[mid]<K)
{
l=mid;//这种写法具有局限性，会出现死循环的情况
}
if(num[mid]<K)
{
l=mid+1;//这种写法可以避免死循环
}
二，在c++stl库中有两个函数可以实现二分的功能
1.std::lower_bound(begin, end, i)
它的作用是查找区间中不小于i的数的，要注意的是该函数返回的是地址，因此需要用指针来获取返回值。
实际使用时如下
#include<iostream>
#include<algorithm>
using namespace std;
int num[10000];
int n,m;
int *p;
int binary_search()
{
p=lower_bound(num,num+n,m);
return 0;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>num[i];
}
sort(num,num+n);
binary_search();
cout<<*p;
return 0;
}
2.std::upper_bound(begin, end, i)
这个函数无论是使用格式还是效果与lower_bound函数都极其相似，不过此函数返回的是大于i的位置，而lower_bound函数返回的是大于等于i的位置，这一点需要注意。
在运用二分查找前，我们需要保证查找的序列时有序的。因此二分查找常常搭配sort函数使用，但要注意的事，并非只有满足升降序才是有序的，若某侧的值都满足某一条件，而另一侧不满足该条件，也可以认为是有序的，这是广义上的有序。
以上就是本文的全部内容，如果能帮助到阅读本文的各位，笔者就非常满足了，如果发现本文所述有误，恳请指出，笔者一定会及时修正。谢谢大家
|