0分求调

awdfkewd @ 2024-08-25 10:01:53

#include<iostream>
using namespace std;
const int MAXN=1e-6;
long long n,m,a[MAXN+10];
long long mid,l,r,t;
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){cin>>a[i];};
    for(int i=0;i<m;i++){
        cin>>t;
        l=0;r=n;
        mid=(l+r)/2;
        while(l<r){
            if(a[mid]==t){
                cout<<mid+1<<endl;
                break;
            }else if(a[mid]>t){
                r=mid;
            }else{
                l=mid;
            }
            mid=(l+r)/2;
        }
        if(a[mid]==t){
            continue;
        }
        cout<<-1<<endl;
    }   
}

by awdfkewd @ 2024-08-25 10:02:21

@awdfkewd 案例最后的6死活不输出，自己编的很成功

by hhztl @ 2024-08-25 10:13:47

@awdfkewd 1e-6是啥，不该是1e6吗

by awdfkewd @ 2024-08-25 10:51:24

@hhztl 这个写法好像都可以，就是那个输出是第一个1第二个3（错误），第三个不输出

by __Luna__ @ 2024-08-25 10:59:54

以下是调过的代码：

#include<iostream>
using namespace std;
const int MAXN=1e6;
long long n,m,a[MAXN+10];
long long mid,l,r,t;
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){cin>>a[i];};
    for(int i=0;i<m;i++){
        cin>>t;
        l=0;r=n;
        mid=(l+r)/2;
        while(l<r){
            if(a[mid]>=t){
                r=mid;
            }else{
                l=mid+1;
            }
            mid=(l+r)/2;
        }
        if(a[mid]==t){
            cout<<mid+1<<" ";
            continue; 
        }
        cout<<-1<<" ";
    }   
}

看以下和你原来的代码有什么区别。
1.1e-6=>1e6
数据范围是10^6，不是10^{-6}呢~
另外其实MAXN+10完全可以改成MAXN，因为你的数组以0为第一个下标。不过这个没有关系。
MAXN=1e-6和a=MAXN+10，你其实定义了一个只有10个数字的数组……
2.l=mid=>l=mid+1
为什么样例第三个询问会死循坏？考虑l=5（a[l]=5），r=6（a[r]=7），由于整数除法的自动向下取整，mid=5。显然a[mid]<t，然后你会把原本就是5的l重新赋值为mid的值，也就是5……
于是，就死循环了。 为了防止这个情况，很简单，把l=mid改成l=mid+1即可（即令二分的两段不重合，你原来的代码会在mid处重合）。
3.a[mid]>t=>a[mid]>=t&a[mid]==t拉出循环
按照你原来的代码，只要a[mid]=t就会输出，但这不能保证a[mid]是第一个符合条件的数的下标（只能保证它是一个符合条件的数的下标）。
基于这个原因，不论mid是否等于t，我们都要继续循环，直到右界和左界重合为止。并且，我们应该优先更新右界，因为我们要找的是最左边的那个解。
在右界和左界重合后，再进行判断，其结果就必定是正确的。

by __Luna__ @ 2024-08-25 11:05:45

哦，还有，<<endl要改成<<" "，因为注意看，题目要求输出仅一行。

by __Luna__ @ 2024-08-25 11:11:41

恭喜你已经会了查找了，不妨来再做一道题目练练手吧!

by __Luna__ @ 2024-08-25 11:13:18

呃，打错了，链接打成了图片（Markdown好久没用了）： https://www.luogu.com.cn/problem/P3369

by awdfkewd @ 2024-08-25 11:20:56

@GodForever 谢谢

by awdfkewd @ 2024-08-25 11:27:50

@GodForever 康不懂我只会普通二叉树awa

by __Luna__ @ 2024-08-25 12:56:48

@awdfkewd 我给的这道题就是一个二叉查找树。
只不过，由于这个数列是动态建立的，为了防止复杂度退化，你需要适时调整树的形态。