0分求助T^T

P2249 【深基13.例1】查找

TKteacake @ 2024-05-13 13:30:34

#include <bits/stdc++.h>
#define ll  long long
using namespace std;
ll a[1000010];
int le;
ll tar;
int tt;

bool check(int mid)
{
    return tar <= a[mid];
}

int solve()
{
    cin >> tar;
    int l = 0 ,r = le - 1;
    int mid;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        //cout << "tar = " << tar << "mid = " << mid << "\n";
//      if (a[mid] == tar)
//      {
//          return mid;
//      }
        if (check(mid))
        {
            r = mid - 1;
        }
        else l = mid + 1;
    }
    if (a[mid] != tar)
    {
        return -1;
    }
    return r + 2;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> le;
    cin >> tt;
    for (int i = 0; i < le; i ++)
    {
        cin >> a[i];
    }
    while (tt--)
    {
        cout << solve() << " ";
    }
}

by dongzhen @ 2024-05-13 13:56:59

你这二分有时候返回值错误

hack:
3 1 
1 2 3
2

改了一下二分,注意小于和等于分开判断

int solve(){
    cin >> tar;
    int l = -1 ,r = le;
    int mid,ans=INT_MAX;
    while (l<r-1){
        mid = (l+r)>>1;
        if (tar<a[mid]){r=mid;}
        else if(tar==a[mid]){ans=min(ans,mid);r=mid;}
        else l=mid;
    }if(ans==INT_MAX){ans=-2;}
    return ans+1;
}

by chenxinye @ 2024-05-13 13:59:03

有必要这么做吗?


|