Search This Blog

Binary lowerbound & upperbound

#include<bits/stdc++.h>
using namespace std;
int ar[10]={1,2,3,4,5,6,7,8,9,10};
int lowerbound(int lo, int hi, int k){
    while(lo<hi){
        int mid=(lo+hi)/2;
        if(ar[mid]>=k) hi=mid;
        else lo=mid+1;
    }
    return hi;
}
int upperbound(int lo, int hi, int k){
    while(lo<hi){
        int mid=(lo+hi)/2;
        if(ar[mid]>k) hi=mid;
        else lo=mid+1;
    }
    return hi;
}
int main()
{
    printf("%d", lowerbound(0,10,4));
    return 0;
}

No comments

Powered by Blogger.