Followed BFS Approach and Overall time complexity - O(log n)


#1

Let me know if you have any doubt for this. Seems bit complex

struct result {
    bool ans;
    int mid,start,end;
}; 
struct result find(const vector<int> &arr, int B, int &min, int &max, int start, int end){
    struct result r;
    r.ans = false;
    while(start < end){
        int mid = start + (end-start)/2;
        if(arr[mid] == B){
            if(min > mid) min = mid;
            if(max < mid) max = mid;
            r.ans = true;
            r.mid = mid; 
            r.start = start;
            r.end = end;
            return r;
        } else if(arr[mid] > B) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    if(start == end && arr[start] == B){
        if(max < start) max = start;
        if(min > start) min = start;
        return r;
    }
    return r;
}

vector<int> Solution::searchRange(const vector<int> &arr, int B) {
    int start = 0;
    int end = arr.size() -1 ;
    int max = INT_MIN, min = INT_MAX;
    struct result r = find(arr,B,min,max,start,end);
    std::queue<struct result> queue;
    queue.push(r);
    while(!queue.empty()){
        struct result t = queue.front();
        queue.pop();
        if(t.ans){
            queue.push(find(arr,B,min,max,t.start,t.mid-1));
            queue.push(find(arr,B,min,max,t.mid+1,t.end));
        }
    }
    std::vector<int> a;
    if(max == INT_MIN && min == INT_MAX){
        a.push_back(-1);a.push_back(-1);
        return a;
    } else if(max == INT_MIN) {
        a.push_back(min);a.push_back(min);
        return a;
    } else if(min == INT_MAX){
        a.push_back(max);a.push_back(max);
        return a;
    } else {
        a.push_back(min);a.push_back(max);
        return a;
    }
    
    
}