洛谷-P2249 【深基13.例1】查找

洛谷 二分

再刷二分模板题原题链接

二分(1)

int bsearch(int l ,int r)
{
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check (mid) ) l = mid;
        else r = mid - 1;
    }
    return mid;
}

二分(2)

int bsearch(int l ,int r)
{
    while(l > r)
    {
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid + 1;
        else r = mid;
    }
    return l;
}

C++ 代码

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false), cin.tie(0)
#define sd(n) scanf("%d",&n)
#define rep(i,a,n) for(int i = a; i <= n ; i++)
#define per(i,a,n) for(int i = n; i>= a; i--)
#define debug(x) cout << #x << ": " << x << endl
#define MOD 1000000007  
#define INF 0x3f3f3f3f  
typedef long long ll;
using namespace std;
const int N = 1e6 + 10;
int n , m , a[N] ;
int bsearch(int l ,int r, int x)
{
    while(l < r)
    {
        int mid = l + r >> 1;
        if( x > a[mid]) l = mid + 1;
        else r = mid;
    }
    if(a[l] != x) return -1;
    return l;
}
int main()
{
    ios;
    cin >> n >> m;
    rep(i , 1, n)
        cin >> a[i];
    rep(i , 1, m)
    {
        int x;
        cin >> x;
        cout << bsearch(1, n , x) << ' ';
    }
    // cout << endl;
    return 0;
}