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

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 2

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 3

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 4

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 5

// 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 6

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.