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

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 2

Arguably a duplicate of Finding closest match in collection of numbers.

Answer 3

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...
      nearest = array[i];
    }
  }
}
return nearest;

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

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 6

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 7

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 8

   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 9

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));