Simple solution in C++ to make your life easier

interview-questions
programming
Tags: #<Tag:0x00007f242207cd38> #<Tag:0x00007f242207cbf8>

#1

vector Solution::searchRange(const vector &A, int B) {

vector<int> C{-1,-1};               // initially no match

if(A.size() == 1 && B == A[0])      // only one element is present
{
    C[0] = 0;
    C[1] = 0;
    return C;
}

int low = 0;
int high = A.size() - 1;
int mid;
while(low <= high)
{
    mid = low + (high-low)/2;
    if(B<A[mid])
    {
        high = mid-1;
    }
    else if(B>A[mid])
    {
        low = mid + 1;
    }
    else                            
    {
        // move low and high until the elements at low and 
        // high are not equal to the mid element
        while(A[low] < A[mid])
        {
            low++;
        }
        while(A[high] > A[mid])
        {
            high--;
        }
        C[0] = low;
        C[1] = high;
        return C;
    }
}
return C;       // If not matched

}


#2

Worst case time complexity will be O(n) in your case for an array having all elements as B
Ex - Element to be found is 5 and array can be
[5,5,5,5,5,5,5,5,5,5,5,5,5]

For such example you will find middle element but then for low and high you have to go till first and last element of an array giving time-complexity as O(n)