Floor in a Sorted Array

Question

I have a sorted array arr[] of size n without duplicates, and given a value x. Floor of x is defined as the largest element K in arr[] such that K is smaller than or equal to x. Find the index of K(0-based indexing).

Input:

n = 7
x = 0
arr[] = {1,2,8,10,11,12,19}

Output:

1

I have to solve it in O(logn). The code which I have below passes the test cases but it's showing time limit exceeded. What is wrong with this code?

static int findFloor(long arr[], int n, long x) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] > x) {
            if (mid != 0 && arr[mid - 1] < x) {
                return mid;
            } else {
                high = mid - 1;
            }
        } else if (arr[mid] < x) {
            low = mid + 1;
        }
    }
    return -1;
}

Answer 1

Your program will stuck in infinite for the case arr[mid] == x as you haven't handled this case. Also, I don't see this program work properly for other cases also.

For example, if I give x=7, this will return the index 2, which is wrong. The correct index should be 1 as x=7 is greater then arr[1] == 2 and less than arr[2] == 8.

Also, your code will break if I give a input of greater than the last element in the array, say x=50 in your example. You'll get an ArrayIndexOutOfBoundException as your low will increase and make the mid index out of bound.

I've corrected the aforementioned cases and the fixed function is like below:

static int findFloor(long[] arr, int n, long x) {
    if (x >= arr[arr.length - 1]) {
        return arr.length - 1;
    }
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] > x) {
            if (mid != 0 && arr[mid - 1] < x) {
                return mid;
            } else {
                high = mid - 1;
            }
        } else {
            if (arr[mid] == x || (mid != 0 && arr[mid + 1] > x)) {
                return mid;
            } else {
                low = mid + 1;
            }
        }
    }
    return -1;
}

Hope you got your answer.