Solution using recursive binary search

int binSearch(const vector<int> &arr, int k, int low, int high){
if(low>high) return -1;
int mid = low + (high-low)/2;

if(arr[mid] == k) return mid;
if(k>arr[mid])return binSearch(arr, k, mid+1, high);
return binSearch(arr, k, low, mid-1);
}

vector<int> Solution::searchRange(const vector<int> &arr, int k) {
int n = arr.size();
int left, right;
left = binSearch(arr, k, 0, n-1);
right = left;

if(left != -1){
    int curLeft = left, curRight =  right;
    while(curLeft != -1 || curRight != -1){
        if(curLeft != -1){
            curLeft = binSearch(arr, k, 0, curLeft-1);
            if(curLeft != -1) left = curLeft;
        }
    
        if(curRight != -1){
            curRight = binSearch(arr, k, curRight + 1, n-1);
            if(curRight != -1) right = curRight;
        }
    }
}

vector<int> ans;
ans.push_back(left);
ans.push_back(right);

return ans;
}
Click here to start solving coding interview questions