Find closest value in an ordererd list

Question

Hi all,

I am wondering how you would write a simple java method finding the closet Integer to a given value in a sorted Integer list.

Here is my first attempt:

public class Closest {

    private static List<Integer> integers = new ArrayList<Integer>();

    static {
     for (int i = 0; i <= 10; i++) {
      integers.add(Integer.valueOf(i * 10));
     }
    }

    public static void main(String[] args) {

     Integer closest = null;
     Integer arg = Integer.valueOf(args[0]);

     int index = Collections.binarySearch(
       integers, arg);

     if (index < 0) /*arg doesn't exist in integers*/ {
      index = -index - 1;
      if (index == integers.size()) {
       closest = integers.get(index - 1);
      } else if (index == 0) {
       closest = integers.get(0);
      } else {
       int previousDate = integers.get(index - 1);
       int nextDate = integers.get(index);
       if (arg - previousDate < nextDate - arg) {
        closest = previousDate;
       } else {
        closest = nextDate;
       }
      }
     } else /*arg exists in integers*/ {
      closest = integers.get(index);
     }
     System.out.println("The closest Integer to " + arg + " in " + integers
       + " is " + closest);
    }
}

What do you think about this solution ? I am sure there is a cleaner way to do this job ...

Maybe such method exists somewhere in the Java libraries and I missed it ??

Manu

Answer 1

Certainly you can simply use a for loop to go through the and keep track of the difference between the value you are on and the value. It would look cleaner, but be much slower.

See: http://stackoverflow.com/questions/445782/finding-closest-match-in-collection-of-numbers/445826#445826

Answer 2

try this little method:

public int closest(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;
}

some testcases:

private final static List<Integer> list = Arrays.asList(10, 20, 30, 40, 50);

@Test
public void closestOf21() {
    assertThat(closest(21, list), is(20));
}

@Test
public void closestOf19() {
    assertThat(closest(19, list), is(20));
}

@Test
public void closestOf20() {
    assertThat(closest(20, list), is(20));
}

Answer 3

I think what you have is about the simplest and most efficient way to do it. Finding the "closest" item in a sorted list isn't something that is commonly encountered in programming (you typically look for the one that is bigger, or the one that is smaller). The problem only makes sense for numeric types, so is not very generalizable, and thus it would be unusual to have a library function for it.

Answer 4

Not tested

int[] randomArray; // your array you want to find the closest
        int theValue; // value the closest should be near to

        for (int i = 0; i < randomArray.length; i++) {
            int compareValue = randomArray[i];

            randomArray[i] -= theValue;
        }

        int indexOfClosest = 0;
        for (int i = 1; i < randomArray.length; i++) {
            int compareValue = randomArray[i];

            if(Math.abs(randomArray[indexOfClosest] > Math.abs(randomArray[i]){
                indexOfClosest = i;
            }
        }

Answer 5

I think your answer is probably the most efficient way to return a single result.

However, the problem with your approach is that there are 0 (if there is no list), 1, or 2 possible solutions. It's when you have two possible solutions to a function that your problems really start: What if this is not the final answer, but only the first in a series of steps to determine an optimal course of action, and the answer that you didn't return would have provided a better solution? The only correct thing to do would be to consider both answers and compare the results of further processing only at the end.

Think of the square root function as a somewhat analogous problem to this.

Answer 6

To solve the problem, I'd extend the Comparable Interface by a distanceTo method. The implementation of distanceTo returns a double value that represents the intended distance and which is compatible with the result of the compareTo implementation.

The following example illustrates the idea with just apples. You can exchange diameter by weight, volume or sweetness. The bag will always return the 'closest' apple (most similiar in size, wight or taste)

public interface ExtComparable<T> extends Comparable<T> {
   public double distanceTo(T other);
}

public class Apple implements Comparable<Apple> {
   private Double diameter;

   public Apple(double diameter) {
      this.diameter = diameter;
   }

   public double distanceTo(Apple o) {
      return diameter - o.diameter;
   }

   public int compareTo(Apple o) {
      return (int) Math.signum(distanceTo(o));
   }
}

public class AppleBag {
   private List<Apple> bag = new ArrayList<Apple>();

   public addApples(Apple...apples){
      bag.addAll(Arrays.asList(apples));
      Collections.sort(bag);
   }

   public removeApples(Apple...apples){
      bag.removeAll(Arrays.asList(apples));
   }

   public Apple getClosest(Apple apple) {
      Apple closest = null;
      boolean appleIsInBag = bag.contains(apple);
      if (!appleIsInBag) {
         bag.addApples(apple);
      }

      int appleIndex = bag.indexOf(apple);
      if (appleIndex = 0) {
         closest = bag.get(1);
      } else if(appleIndex = bag.size()-1) {
         closest = bag.get(bag.size()-2);
      } else {
         double absDistToPrev = Math.abs(apple.distanceTo(bag.get(appleIndex-1));
         double absDistToNext = Math.abs(apple.distanceTo(bag.get(appleIndex+1));
         closest = bag.get(absDistToNext < absDistToPrev ? next : previous);
      }

      if (!appleIsInBag) {
         bag.removeApples(apple);
      }

      return closest;
   }
}

Answer 7

If you're not massively concerned on performance (given that the set is searched twice), I think using a Navigable set leads to clearer code:

public class Closest
{
  private static NavigableSet<Integer> integers = new TreeSet<Integer>();

  static
  {
    for (int i = 0; i <= 10; i++)
    {
      integers.add(Integer.valueOf(i * 10));
    }
  }

  public static void main(String[] args)
  {
    final Integer arg = Integer.valueOf(args[0]);
    final Integer lower = integers.lower(arg);
    final Integer higher = integers.higher(arg);

    final Integer closest;
    if (lower != null)
    {
      if (higher != null)
        closest = (higher - arg > arg - lower) ? lower : higher;
      else
        closest = lower;
    }
    else
      closest = higher;

    System.out.println("The closest Integer to " + arg + " in " + integers + " is " + closest);
  }
}

Answer 8

Your solution appears to be asymptotically optimal. It might be slightly faster (though probably less maintainable) if it used Math.min/max. A good JIT likely has intrinsics that make these fast.

int index = Collections.binarySearch(integers, arg);
if (index < 0) {
    int previousDate = integers.get(Math.max(0, -index - 2));
    int nextDate = integers.get(Math.min(integers.size() - 1, -index - 1));
    closest = arg - previousDate < nextDate - arg ? previousDate : nextDate;
} else {
    closest = integers.get(index);
}