Binary Search

Binary Search - Different variations

// return index of first element >= target
int lower_bound(vector<int> v, int target){
    int l = 0;
    int r = v.size();
    while(l < r) {
        int m = l+(r-l)/2;
        v[m] < target ? l = m+1 : r = m;
    }
    return l;
}

// return index of first element > target
int upper_bound(vector<int> v, int target){
    int l = 0;
    int r = v.size();
    while(l < r) {
        int m = l+(r-l)/2;
        v[m] <= target ? l = m+1 : r = m;
    }
    return l;
}

// return index of element == target
int binary_search(vector<int> v, int target){
    int l = 0;
    int r = v.size();
    while(l < r) {
        int m = l+(r-l)/2;
        v[m] < target ? l = m+1 : r = m;
    }
    return l < v.size() && v[l] == target ? l : -1;
}

int main()
{
    vector<int> v = {1,1,2,4,5,5,5,6,6,8,9};
    cout<< lower_bound(v, 5);  // 4
    cout<< upper_bound(v, 5);  // 7
    return 0;
}