CODEWITHSUNDEEP
javasearch
Haych
Haych

Reputation: 942

Search for the index of an array with the closest Value to N - Java

Can anyone offer any advice as to how you can search an Array for the closest value to N of an unordered array without using API classes? I don't want my algorithm to be linear time.

Would one way to do this be to order the array and then do an binary-chop search?

Are the any more efficient methods to doing this?

Upvotes: 0

Views: 98

Answers (2)

Erwin Bolwidt
Erwin Bolwidt

Reputation: 31269

As @ThomasPastircak wrote, you're not going to get better than linear time performance if your array is unsorted.

Inserting the data in your array into another data structure is going to have at least linear complexity (as all elements of your array need to be inserted into it) and sorting it will also have worse than linear complexity.

There is not much different between your question and the question "How can I search for the maximum/minimum number in an unsorted array?". You're just searching for the minimum difference with your reference value N.

A simple solution for it is:

public static int closest(double[] array, double n) {
    double leastDifference = Double.POSITIVE_INFINITY;
    int indexOfLeastDifference = -1;
    for (int a = 0; a < array.length; a++) {
        double difference = Math.abs(array[a] - n);
        if (difference < leastDifference) {
            indexOfLeastDifference = a;
            leastDifference = difference;
        }
    }
    return indexOfLeastDifference;
}

Upvotes: 1

Tomas Pastircak
Tomas Pastircak

Reputation: 2857

If any collection is unsorted, you cannot really "guess" where the element is going to be and the complexity is always going to be linear.

Array is probably not the best option for you - you may want to use either TreeSet, which provides methods lower() and higher() from NavigableSet interface, these methods have logarithmic complexity. However, be aware that it won't contain duplicate elements, but I think it should be OK for the stuff you need.

Upvotes: 1

Related Questions