Binary Search

Find a Specific Key

int my_binary_search(int key)
{
    int L = LOWER_BOUND, R = UPPER_BOUND;
    while ( L <= R ) {
        int M = L + ((R - L) >> 1);
        if ( arr[M] == key )
            return M;
        if ( arr[M] < key )
            L = M + 1;
        else
            R = M - 1;
    }
    return -1;  // key is not present
}

Find a "Gap"

bool is_valid(int val)
{
    /* return true if "val" is valid */
}

int my_binary_search()
{
    int L = LOWER_BOUND, R = UPPER_BOUND;
    while ( L + 1 < R ) {
        int M = L + ((R - L) >> 1);
        if ( is_valid(M) )
            L = M;
        else
            R = M;
    }
    return L;
}