二分方法+优化(O(n))
这道题普通二分的复杂度O(n*logn)
这里定义p记录一下,每一次的二分都减少,每一次二分都在上一次的基础上.这样可以让复杂度为O(n)的级别
注意:这里的二分如果没有没有查找到对应的值,则最后的r和l的值是大于目标值的最小值的下标(正是通过这点来优化)
( 新手哈,代码可能写的有点粗糙 )
//代码^^
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 100010;
int a[N],b[N];
int main()
{
int n,m,x;
scanf("%d%d%d",&n,&m,&x);
for(int i = 0;i < n;i ++) scanf("%d",&a[i]);
for(int i = 0;i < m;i ++) scanf("%d",&b[i]);\
int p=m-1;
for(int i = 0;i < n;i ++)
{
if(a[i] < x)
{
int l = 0,r =p;
int c = x - a[i];
while(l < r)
{
int mid = (l + r) / 2;
if(c > b[mid]) l = mid + 1;
else r = mid;
}
if(c == b[r]) printf("%d %d",i,r);
p=r;
}
}
return 0;
}