#include <vector>
#include <iostream>

using namespace std;

//Find the last element, whose value is less than target, in a sorted array 
int BSearchLowerBound(int array[], int low, int high, int target)
{
    if(high < low  || target <= array[low]) return -1;
	
    int mid = (low + high + 1) / 2; //make mid lean to large side
    while (low < high)
    {
        if (array[mid] < target)
            low = mid;
        else
            high = mid - 1;
		
		mid = (low + high + 1) / 2;
    }

    return mid;
}

//Find the fisrt element, whose value is larger than target, in a sorted array 
int BSearchUpperBound(int array[], int low, int high, int target)
{
    if(low > high || target >= array[high]) return -1;
    
    int mid = (low + high) / 2;
    while (high > low)
    {
        if (array[mid] > target)
            high = mid;
        else
            low = mid + 1;
		
		mid = (low + high) / 2;
    }

    return mid;
}

vector<int> SearchRange(int A[], int n, int target) 
{
    vector<int> r(2, -1);
    if (n <= 0) return r;
    
    int lower = BSearchLowerBound(A, 0, n-1, target);
    lower = lower + 1; //move to next element

    if(A[lower] == target)
        r[0] = lower;
    else //target is not in the array
        return r;

    int upper = BSearchUpperBound(A, 0, n-1, target);
    upper = upper < 0? (n-1):(upper - 1); //move to previous element

    //since in previous search we had check whether the target is
    //in the array or not, we do not need to check it here again
    r[1] = upper;
	
	return r;
}


int main(int argc, char** argv)
{
    int A[] = {1,2,3,3,3,3,4,5,6,7};

    vector<int> v;
	int size = sizeof(A)/sizeof(int);
	
    int target = 0;
    v = SearchRange(A, size, target);
    cout << target << ": " << v[0] << ',' << v[1] << '\n';
	
    target = 1;
    v = SearchRange(A, size, target);
    cout << target << ": " << v[0] << ',' << v[1] << '\n';
	
    target = 3;
    v = SearchRange(A, size, target);
    cout << target << ": " << v[0] << ',' << v[1] << '\n';
	
    target = 7;
    v = SearchRange(A, size, target);
    cout << target << ": " << v[0] << ',' << v[1] << '\n';
	
    target = 8;
    v = SearchRange(A, size, target);
    cout << target << ": " << v[0] << ',' << v[1] << '\n';
	
    return 0;
}