Find the nearest/closest value in a sorted List

java logic
drBet picture drBet · May 14, 2015 · Viewed 40.3k times · Source

I was wondering if it is possible to find the closest element in a List for a element that is not there.

For example if we had the values [1,3,6,7] and we are looking for the element closest to 4, it should return 3, because 3 is the biggest number in the array, that is smaller than 4.

I hope it makes sense, because English is not my native language.

Answer

David Soroko picture David Soroko · May 14, 2015

If the array is sorted you can do a modified binary search in O( log n ) : 

    public static int search(int value, int[] a) {

        if(value < a[0]) {
            return a[0];
        }
        if(value > a[a.length-1]) {
            return a[a.length-1];
        }

        int lo = 0;
        int hi = a.length - 1;

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

            if (value < a[mid]) {
                hi = mid - 1;
            } else if (value > a[mid]) {
                lo = mid + 1;
            } else {
                return a[mid];
            }
        }
        // lo == hi + 1
        return (a[lo] - value) < (value - a[hi]) ? a[lo] : a[hi];
    }

Related questions

Fastest way of finding the middle value of a triple?

Given is an array of three numeric values and I'd like to know the middle value of the three. The question is, what is the fastest way of finding the middle of the three? My approach is this kind of …

Read More
In Java, what are the boolean "order of operations"?

Let's take a simple example of an object Cat. I want to be sure the "not null" cat is either orange or grey. if(cat != null && cat.getColor() == "orange" || cat.getColor() == "grey") { //do stuff } I believe AND comes …

Read More
Fastest way to get sign in Java?

I'd like to get the sign of a float value as an int value of -1 or 1. Avoiding conditionals is always a good idea in reducing computational cost. For instance, one way I can think of would be to use …

Read More