Easiest way to search for starting and ending indices using lower_bound or upper_bound

help
,
1

Consider I have an array of integer which is sorted.

And I want the starting index of the first number >= L.
and I want the ending index of the last number <= R.

I was solving a question in which it required the usage of this.
I implemented using lower_bound, but I ended up using too many if, else conditions.

My Implementation 
    auto it = lower_bound(v.begin(), v.end(), L );
    auto it1 = lower_bound(v.begin(), v.end(), R );

    if( it == v.end() or *it > R or *it < L){
        //No valid found; return;
    } 
    if( it1 != v.begin() and (it1 == v.end() or *it1 > R) ){
          it1--;
    }

    if( it1 != v.end() and ( *it1 > R or *it1 < L ) ){
        //No valid found; return;
    }
    int start_id = it - v.begin();
    int end_id = it1 - v.begin();

   if(start_id < 0 or start_id > N or end_id < 0 or end_id > N){
         //No valid found; return;
   } else {
         //Correct
   }

Is there any cleaner and less if, else conditions implementation?

Thank you :slight_smile:

2

I haven’t tested the code, but how about ?

void someFancyFunc (deque<int>& arr, int L, int R) {
    #define inf R+1
    // Assuming L <= R
    arr.push_front(L-1);
    arr.push_back(inf);
    int left = lower_bound(arr.begin(), arr.end(), L) - arr.begin();
    int right = prev(upper_bound(arr.begin(), arr.end(), R)) - arr.begin();
    // check if indices are valid using arr.size()
    // appropriate return statement.
}
3 Likes
3

This is the cleanest I can think of.

Code 
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
void solve(){
    int n, Q;
    cin>>n>>Q;
    vector<int> seq(n);
    for(auto &x : seq){
        cin>>x;
    }
    auto valid=[&](int idx){return idx>=0 && idx<n;};
    while(Q--){
        int l,r;
        cin>>l>>r;
        int lidx=lower_bound(seq.begin(), seq.end(), l) - seq.begin();
        int ridx=upper_bound(seq.begin(), seq.end(), r) - seq.begin() - 1;
        if(valid(lidx) && valid(ridx)){
            cout<<lidx + 1<<" "<<ridx + 1<<"\n";
        }
        else{
            cout<<":(\n";
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}
2 Likes