Only less than 10% programmers all over the world can get it right.

binary_search.c

int binary_search_first_position(int *A, int n, int target)  
{   
    int low = -1, high = n;
    assert(A != NULL && n >= 0);
    while (low + 1 < high)
    {
        int mid = (low + high) >> 1;
        if (A[mid] < target)
            low = mid;
        else
            high = mid;
    }
 
    if (high >= n || A[high] != target)
        return -high - 1;
    else
        return high;  // high == low + 1
}


int binary_search_last_position(int *A, int n, int target)  
{
    int low = -1, high = n;
    assert(A != NULL && n >= 0);
    while (low + 1 < high)
    {
        int mid = (low + high) >> 1;
        if (A[mid] > target)
            high = mid;
        else
            low = mid;
    }
 
    if (low < 0 || A[low] != target)
        return -low - 2;
    else
        return low;  // low == high - 1
}