Find the first element in a sorted array that is smaller than the target

Question

In a sorted array, you can use binary search to perform many different kinds of operations:

1. to find the first element smaller than the target
2. to find the first element bigger than the target or,
3. to find the first element smaller or equal than the target
4. to find the first element bigger or equal than the target or even specific
5. to find the element closest to the target.

You can find answers to #2 and #5 in stack overflow, the answer of which are using mutations of binary search, however there is no fixed algorithm to answer those questions, specifically in adjusting the indices.

For example, in question 3, find the first smaller or equal element in sorted array than target: Given int[] stocks = new int[]{1, 4, 3, 1, 4, 6};, I want to find the first element smaller than 5. It should return 4 after sorting and my code goes like:

private static int findMin(int[] arr, int target) {
    Arrays.sort(arr);
    int lo = 0;
    int hi = arr.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] > target) {
            hi = mid - 1;
        } else {
            lo = mid;
        }
    }
    return lo;
}

The logic here is:

1. if you find mid element equals to target, you just return the mid
2. if you find mid element bigger than the target, you just discard the mid and everything bigger than it
3. if you find mid element is smaller than the target, the mid element could be an answer, you want to keep it, but discard anything smaller than it.

If you run it, it actually goes into a infinite loop, but just tweak the start index of hi = arr.length - 1 to hi = arr.length;, it actually works well. I have no clue how to really set all the conditions up: how to write conditions, what to set start index of hi and lo and use lo<=hi or lo < hi.

Any help?

Answer 1

Basically in the above mentioned case ,you need the greatest element which is smaller than the given value, i.e you need to find floor of the given element. This can be easily done using binary search in O(logn), time :

The cases which you need to consider are as follows:

1. If last element is smaller than x, than return the last element.

2. If middle point is floor, than return mid.

3. If element is not found in both of the above cases, than check if the element lies between mid and mid -1. If it is so than return mid-1.
4. Else keep iterating on left half or right half until you find a element that satisfies your condition. Select right half or left half based on the check that given value is greater than mid or less than mid.

Try the following:

static int floorInArray(int arr[], int low, int high, int x)
{
    if (low > high)
        return -1;

    // If last element is smaller than x
    if (x >= arr[high])
        return high;

    // Find the middle point
    int mid = (low+high)/2;

    // If middle point is floor.
    if (arr[mid] == x)
        return mid;

    // If x lies between mid-1 and mid
    if (mid > 0 && arr[mid-1] <= x && x < arr[mid])
        return mid-1;

    // If x is smaller than mid, floor
    // must be in left half.
    if (x < arr[mid])
        return floorInArray(arr, low, mid - 1, x);

    // If mid-1 is not floor and x is
    // greater than arr[mid],
    return floorInArray(arr, mid + 1, high,x);
}