提问:如何在一组数组中查找到我们想要的数。答案有很多,首先最最最广为人知的便是循环查找,简而言之循环一边数组中的每个数。
然而,当数据很大的时候,这种方式会面临超时的危险,所以借此引出我们的今天的主人公:二分法。
看一下题目
给定一个按照升序排列的长度为 n的整数数组,以及 q个查询。
对于每个查询,返回一个元素 k的起始位置和终止位置(位置从 00 开始计数)。
如果数组中不存在该元素,则返回 -1 -1。
输入格式
第一行包含整数 n和 q,表示数组长度和询问个数。
第二行包含 n个整数(均在 1∼100001∼10000 范围内),表示完整数组。
接下来 q行,每行包含一个整数 k,表示一个询问元素。
输出格式
共 q行,每行包含两个整数,表示所求元素的起始位置和终止位置。
如果数组中不存在该元素,则返回 -1 -1。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
题目的数据较大,暴力写法非智者之道,看一下二分的解法 :二分,说白了就是通过不断折中的方法找到某一性质的边界。
且看上面的两个性质,蓝色表示大于等于x,红色表示小于等于x。
先看第一张图,我们先抓住数组的开头结尾,进行第一次“腰斩”,mid=(l+r)/2,此时会发生两种情况,数组的元素q[mid]处于蓝色性质中,或在蓝色性质之外。当在蓝色之中时,我们需要使mid往左移,所以右边界r=mid。当在蓝色之外时,我们需要将mid往右移,左边界l=mid+1(不能等于mid,否则将死循环,并且因为不在蓝色中,需要+1来更进一步)。
看第二张图,原理与上述类似,红色之内l=mid,红色之外r=mid+1_,注意:在进行红色的“腰斩”时,我们应该将式子变为 mid=(l+r+1)/2_,因为我们的算法的除法性质是向下取整的,(3/2=1(int类型)),如果仍为原式,mid将永远无法到达红色性质的边界,代码将陷入死循环。
最终的解题代码如下:
#include<iostream>
using namespace std;
const int N=1000010;
int n,m;
int q[N];
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>q[i];
while(m--)
{
int x;
cin>>x;
int l=0,r=n-1;
while(l<r)
{
int mid=l+r>>1;
if(q[mid]>=x)
r=mid;
else
l=mid+1;
}
if(q[l]!=x)
cout<<"-1 -1"<<endl;
else
{
cout<<r<<" ";
l=0,r=n-1;
while(l<r)
{
int mid=l+r+1>>1;
if(q[mid]<=x)
l=mid;
else
r=mid-1;
}
cout<<l<<endl;
}
}
return 0;
}
希望对大家有帮助。