Find first index of a number in the sorted array containing duplicates

This can be done easily in linear time by making a pass through the array. In coding interviews it is not likely the solution the interviewer is looking for. So we have to do better. We know that binary search provides a efficient solution for finding an element in sorted array. Lets look at the problem to see if we can modify the binary search algorithm to solve this problem. We can start with binary search to find the index. Once we find the index we have to look to the left to check if the number is present. If we look to the left linearly then the solution will be O(n). To do better than that we can use another binary search in the left and continue until we find the fist index where the number occurs.

/**
 * Find first index of the number k in the sorted
 * array x of size n
 */
int first_index(int x[], int n, int k) {
    int lo = 0;
    int hi = n - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo)/2;

        if (x[mid] == k) {
            if (mid > 0 && x[mid - 1] == k) {
                hi = mid - 1;
            } else {
                return mid;
            }

        } else if(x[mid] < k) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return -1;
}