CODEWITHSUNDEEP
javaarraysalgorithm
Neptune
Neptune

Reputation: 627

Java: search the nearest value in array

I have an array of ordered double of big dimension, for example:

[2.1,3.4,3.6,4.1]

Now I generate, in some manner, a double numer, for example:

3.51

I need to make a function in Java that get the array and the number and give me the nearest value in the array of this number. In this example 3.6.

How i can do this in the most efficent way ? Because I can have array of 300000 double and need to do this operation frequently. Then i can't make a simple compare.

Edit: I have make this, in some test the result is correct, for you is correct?

        int pos = Arrays.binarySearch(allTime.times, value);
        double out;

        if(pos >= 0)
        {
//          System.out.println(allTime.times[pos]);
            out = allTime.times[pos];
        }
        else if(pos == -1)
        {
//          System.out.println(allTime.times[0]);
            out = allTime.times[0];
        }
        else
        {
            int insertionPoint = -pos-1;
            if(insertionPoint < allTime.times.length)
            {
                if(allTime.times[insertionPoint] - value < value - allTime.times[insertionPoint-1])
//                  System.out.println(allTime.times[insertionPoint] );
                    out = allTime.times[insertionPoint];
                else
//                  System.out.println(allTime.times[insertionPoint-1] );
                    out = allTime.times[insertionPoint-1];
            }
            else
//              System.out.println(allTime.times[allTime.times.length -1]);
                out = allTime.times[allTime.times.length -1];
        }

Upvotes: 1

Views: 281

Answers (2)

dharam
dharam

Reputation: 106

Jimmy T answer is not handling the corner case, like if the searching number falls before 0th index or if it falls beyond the last index.

Here is the corrected one

     double searchNearest(double[] array, double searchNumber) {
    int pos = Arrays.binarySearch(array, searchNumber);
    if (pos >= 0)
        return searchNumber;
    else {
        int insertionPoint = -pos - 1;
        if (insertionPoint > 0 && insertionPoint < array.length) {
            if ((searchNumber - array[insertionPoint - 1]) < (array[insertionPoint] - searchNumber)) {
                return array[insertionPoint - 1];
            } else {
                return array[insertionPoint];
            }

        } else {

            return insertionPoint == 0 ? array[0] : array[array.length - 1];
        }
    }

}

Upvotes: 1

Jimmy T.
Jimmy T.

Reputation: 4190

Arrays.binarySearch also works for elements not contained in the array.

int pos = Arrays.binarySearch(arr, value);

If the value is not contained it returns a negative value which describes where the value should be: (-(insertion point) - 1).

Then just find which of the two neighbor values is the correct.

if(pos < 0)
{
  int insertionPoint = -pos-1;
  if(insertionPoint == arr.length) //value is bigger than every value in array
    //arr[insertionPoint-1] is the nearest value
  else if(insertionPoint == 0) //value is smaller than every value in array
    //arr[0] is the nearest value
  else if(value-arr[insertionPoint-1] < arr[insertionPoint]-value)
    //arr[insertionPoint-1] is the nearest value
  else
    //arr[insertionPoint] is the nearest value
}else
  //arr[pos] has the same value

The value at index insertPoint is bigger than value. I also handled the case that the value is contained in the array.

Upvotes: 2

Related Questions