2
二分查找进阶版_hanwang的技术博客_51CTO博客
source link: https://blog.51cto.com/u_15740457/5995726
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
时间限制：500ms
空间限制：64MB
很久以前，有位同学，在学完算法课的二分后，激动的振臂高呼：“我学会二分了！”。此时，一位学长从旁边经过听到此话，决定出一道题考考他，挫挫同学的锐气，让这位学弟再去好好刷二分.
学长告诉学弟n个数据，再询问他q次，每次询问告诉学弟一个x，要求学弟在每次询问给出的x的下标。
二、解题思路
那么我们该怎么根据值找下标呢，如果能做到一对一映射，每个值对应一个下标，实际上map可以做到
这个事情，也就是所谓的哈希。但是顺序是乱序，不能进行二分查找（二分查找的前提是顺序）
当然如果不使用map，我们可以尝试把无序的序列变成有序的，这时候查找值，我们就可以采取二分查找，那下标咋办呢，把下标和值绑定在一起就行，开个结构体存下标和值，排序的时间复杂度是 nlog^n ，二分查找的时间复杂度也是 nlog^n ，时间复杂度也在允许范围之内。值得注意的是，数据范围在 long long 之内，注意别爆 int 了（三年ACM一场空，不开longlong见祖宗）
三、源码及注释
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>//sort函数的头文件
using namespace std;
const long long N = 1e6 + 5;//满足题目对n的要求，并且稍微开大一点（+5）
typedef long long ll;//重新定义long long类型，更加方便
ll n, q, x;
struct node
{
ll idx, num;
}arr[N];//创建结构体存储数组中的值和下标
bool cmp(node x, node y)
{
return x.num < y.num;
}//自定义数组元素排序方法
int main()
{
scanf("%lld%lld", &n, &q);//当数据过多时，不采用cout/cin函数，采用scanf和printf函数
for (int i=1;i<=n;i++)
{
scanf("%lld", &arr[i].num);//注意long long的打印格式
arr[i].idx = i;
}
sort(arr+1, arr + n+1,cmp);
for (int i=1;i<=q;i++)
{
scanf("%lld", &x);
ll left = 1;
ll right = n;
ll mid = 0;
while (right >= left)
{
mid = (left + right) / 2;
if (arr[mid].num > x)
{
right=mid-1;//注意最基本的二分查找
}
else if (arr[mid].num < x)
{
left=mid+1;
}
else
{
break;
}
}
if (left <= right)
{
printf("%lld\n", arr[mid].idx);
}
}
return 0;
}
#include<string>
#include<cstdio>
#include<algorithm>//sort函数的头文件
using namespace std;
const long long N = 1e6 + 5;//满足题目对n的要求，并且稍微开大一点（+5）
typedef long long ll;//重新定义long long类型，更加方便
ll n, q, x;
struct node
{
ll idx, num;
}arr[N];//创建结构体存储数组中的值和下标
bool cmp(node x, node y)
{
return x.num < y.num;
}//自定义数组元素排序方法
int main()
{
scanf("%lld%lld", &n, &q);//当数据过多时，不采用cout/cin函数，采用scanf和printf函数
for (int i=1;i<=n;i++)
{
scanf("%lld", &arr[i].num);//注意long long的打印格式
arr[i].idx = i;
}
sort(arr+1, arr + n+1,cmp);
for (int i=1;i<=q;i++)
{
scanf("%lld", &x);
ll left = 1;
ll right = n;
ll mid = 0;
while (right >= left)
{
mid = (left + right) / 2;
if (arr[mid].num > x)
{
right=mid-1;//注意最基本的二分查找
}
else if (arr[mid].num < x)
{
left=mid+1;
}
else
{
break;
}
}
if (left <= right)
{
printf("%lld\n", arr[mid].idx);
}
}
return 0;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK