Finding closest number in an array

Question

In an array first we have to find whether a desired number exists in that or not? If not then how will I find nearer number to the given desired number in Java?

Answer 1

An idea:

int nearest = -1;
int bestDistanceFoundYet = Integer.MAX_INTEGER;
// We iterate on the array...
for (int i = 0; i < array.length; i++) {
  // if we found the desired number, we return it.
  if (array[i] == desiredNumber) {
    return array[i];
  } else {
    // else, we consider the difference between the desired number and the current number in the array.
    int d = Math.abs(desiredNumber - array[i]);
    if (d < bestDistanceFoundYet) {
      // For the moment, this value is the nearest to the desired number...
      bestDistanceFoundYet = d; // Assign new best distance...
      nearest = array[i];
    }
  }
}
return nearest;

Answer 2

//This will work

public int nearest(int of, List<Integer> in)
{
int min = Integer.MAX_VALUE;
int closest = of;

for (int v : in) 
{
    final int diff = Math.abs(v - of);

    if (diff < min) 
    {
        min = diff;
        closest = v;
    }
}
return closest;
}

Answer 3

Another common definition of "closer" is based on the square of the difference. The outline is similar to that provided by romaintaz, except that you'd compute

long d = ((long)desiredNumber - array[i]);

and then compare (d * d) to the nearest distance.

Note that I've typed d as long rather than int to avoid overflow, which can happen even with the absolute-value-based calculation. (For example, think about what happens when desiredValue is at least half of the maximum 32-bit signed value, and the array contains a value with corresponding magnitude but negative sign.)

Finally, I'd write the method to return the index of the value located, rather than the value itself. In either of these two cases:

• when the array has a length of zero, and
• if you add a "tolerance" parameter that bounds the maximum difference you will consider as a match,

you can use -1 as an out-of-band value similar to the spec on indexOf.

Answer 4

If the array is sorted, then do a modified binary search. Basically if you do not find the number, then at the end of search return the lower bound.

Answer 5

Pseudocode to return list of closest integers.

myList = new ArrayList();          

if(array.length==0) return myList; 

myList.add(array[0]);

int closestDifference = abs(array[0]-numberToFind);

for (int i = 1; i < array.length; i++) {

 int currentDifference= abs(array[i]-numberToFind);

  if (currentDifference < closestDifference) {

    myList.clear();

    myList.add(array[i]);

         closestDifference = currentDifference;

  } else {

    if(currentDifference==closestDifference) {

        if( myList.get(0) !=array[i]) && (myList.size() < 2) {

            myList.add(array[i]);

        }
            }

       }

}

return myList;

Answer 6

A few things to point out:

1 - You can convert the array to a list using

Arrays.asList(yourIntegerArray);

2 - Using a list, you can just use indexOf().

3 - Consider a scenario where you have a list of some length, you want the number closest to 3, you've already found that 2 is in the array, and you know that 3 is not. Without checking the other numbers, you can safely conclude that 2 is the best, because it's impossible to be closer. I'm not sure how indexOf() works, however, so this may not actually speed you up.

4 - Expanding on 3, let's say that indexOf() takes no more time than getting the value at an index. Then if you want the number closest to 3 in an array and you already have found 1, and have many more numbers to check, then it'll be faster to just check whether 2 or 4 is in the array.

5 - Expanding on 3 and 4, I think it might be possible to apply this to floats and doubles, although it would require that you use a step size smaller than 1... calculating how small seems beyond the scope of the question, though.

Answer 7

// paulmurray's answer to your question is really the best :

// The least square solution is way more elegant, 
// here is a test code where numbertoLookFor
// is zero, if you want to try ...

import java.util.* ;

public class main {
    public static void main(String[] args) 
    {
        int[] somenumbers = {-2,3,6,1,5,5,-1} ;
        ArrayList<Integer> l = new ArrayList<Integer>(10) ;
        for(int i=0 ; i<somenumbers.length ; i++)
        {
            l.add(somenumbers[i]) ;
        }
        Collections.sort(l, 
                new java.util.Comparator<Integer>()
                {
                    public int compare(Integer n1, Integer n2)
                    {
                        return n1*n1 - n2*n2 ;
                    }
                }
        ) ;
        Integer first = l.get(0) ;
        System.out.println("nearest number is " + first) ;  
    }
}

Answer 8

Array.indexOf() to find out wheter element exists or not. If it does not, iterate over an array and maintain a variable which holds absolute value of difference between the desired and i-th element. Return element with least absolute difference.

Overall complexity is O(2n), which can be further reduced to a single iteration over an array (that'd be O(n)). Won't make much difference though.

Answer 9

Only thing missing is the semantics of closer.

What do you do if you're looking for six and your array has both four and eight?

Which one is closest?

Answer 10

   int d = Math.abs(desiredNumber - array[i]);
    if (d < bestDistanceFoundYet) {
      // For the moment, this value is the nearest to the desired number...
      nearest = array[i];
    }

In this way you find the last number closer to desired number because bestDistanceFoundYet is constant and d memorize the last value passign the if (d<...).

If you want found the closer number WITH ANY DISTANCE by the desired number (d is'nt matter), you can memorize the last possibile value. At the if you can test

if(d<last_d_memorized){ //the actual distance is shorter than the previous
    // For the moment, this value is the nearest to the desired number...
          nearest = array[i];
    d_last_memorized=d;//is the actual shortest found delta 
}

Answer 11

int[] somenumbers = getAnArrayOfSomenumbers();
int numbertoLookFor = getTheNumberToLookFor();

boolean arrayContainsNumber = 
   new HashSet(Arrays.asList(somenumbers))
      .contains(numbertoLookfor);

It's fast, too.

Oh - you wanted to find the nearest number? In that case:

int[] somenumbers = getAnArrayOfSomenumbers();
int numbertoLookFor = getTheNumberToLookFor();

ArrayList<Integer> l = new ArrayList<Integer>(
  Arrays.asList(somenumbers)
);
Collections.sort(l);
while(l.size()>1) {
  if(numbertoolookfor <= l.get((l.size()/2)-1)) {
    l = l.subList(0, l.size()/2);
  }
  else {
    l = l.subList(l.size()/2, l.size); 
  }
}

System.out.println("nearest number is" + l.get(0));

Oh - hang on: you were after a least squares solution?

Collections.sort(l,  new Comparator<Integer>(){
  public int compare(Integer o1, Integer o2) {
    return (o1-numbertoLookFor)*(o1-numbertoLookFor) - 
           (o2-numbertoLookFor)*(o2-numbertoLookFor);
  }});

System.out.println("nearest number is" + l.get(0));