为啥爆零

woyaoAKIOI0924PTY @ 2024-07-14 20:49:32

#include<bits/stdc++.h>
using namespace std;
int n,a[10000005],x,q;
int find(int pos1,int pos2,int x)
{
    int lt=pos1-1,rt=pos2+1;
    while(lt+1<rt)
    {
        int mid=(lt+rt)/2;
        if(a[mid]==x)
            return mid;
        else if(a[mid]<x)
            lt=mid;
        else
            rt=mid;
    }
    return -1;
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    while(q--)
    {
        cin>>x;
        cout<<find(1,n,x)<<" ";
    }
    return 0;
}

by MuYuMC @ 2024-07-15 12:27:06

@woyaoAKIOI0924PTY 为什么要用pos 看看我的代码

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
int A[1000000];
int n,m;
int er(int p)
{
    int l,r,mid,flag = -1;
    l = 1;r = n;
    while(l <= r)
    {
        mid = (l + r) / 2;
        if(A[mid] == p)
        {
            flag = mid;
            r = mid - 1;
        }
        else{
            if(A[mid] < p)
            {
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }

        }
    }
    return flag;
}
int main()
{
    int i,x;
    cin >> n >> m;
    for(i = 1;i <= n;i++)
    {
        cin >> A[i];
    }
    for(i = 1;i <= m;i++)
    {
        cin >> x;
        cout << er(x) << " ";
    }
    return 0;
}

by eggy_LIKE @ 2024-08-16 11:27:19

@woyaoAKIOI0924PTY 其实就是一个经典的二分题目，代码：

#include<bits/stdc++.h>
using namespace std;
int a[1000005], x, n, m;
void solve() {
    cin >> x;  // 输入当前查询的数字
    int l = 1, r = n, ans = -1;  // 初始化二分查找的左右边界和结果
    // 二分查找
    while(l<=r) {
        int mid = l+(r-l)/2;  // 计算中间位置
        if(a[mid] == x) {
            ans = mid;    // 找到目标值
            r = mid-1;  // 缩小右边界
        } else if(a[mid] > x) {
            r = mid-1;  // 缩小右边界
        } else {
            l = mid+1;  // 缩小左边界
        }
    }
    cout << ans << " ";  // 输出结果
}
int main() {
    cin >> n >> m;  // 输入 n 和 m
    for(int i = 1; i <= n; i++) {
        cin >> a[i];  // 输入序列中的 n 个数
    }    
    while(m--) solve(); 
    return 0;
}

by eggy_LIKE @ 2024-08-16 11:29:15

@woyaoAKIOI0924PTY 互关吗

#include<bits/stdc++.h>
using namespace std;
int a[1000005], x, n, m;
void solve() {
    cin >> x;  // 输入当前查询的数字
    int l = 1, r = n, ans = -1;  // 初始化二分查找的左右边界和结果
    // 二分查找
    while(l<=r) {
        int mid = l+(r-l)/2;  // 计算中间位置
        if(a[mid] == x) {
            ans = mid;    // 找到目标值
            r = mid-1;  // 缩小右边界
        } else if(a[mid] > x) {
            r = mid-1;  // 缩小右边界
        } else {
            l = mid+1;  // 缩小左边界
        }
    }
    cout << ans << " ";  // 输出结果
}
int main() {
    cin >> n >> m;  // 输入 n 和 m
    for(int i = 1; i <= n; i++) {
        cin >> a[i];  // 输入序列中的 n 个数
    }    
    while(m--) solve(); 
    return 0;
}