在orderd列表中查找最近的值

试试这个小方法:

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

一些测试案例:

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

我认为你所拥有的是最简单和最有效的方法。在排序列表中查找“最近”的项不是编程中常见的问题(您通常查找较大的项或较小的项)。这个问题只对数字类型有意义,所以不是很可归纳的,因此为它提供一个库函数是不常见的。

为了解决这个问题,我将用一个DistanceTo方法扩展可比较的接口。DistanceTo的实现返回一个表示预期距离的双精度值,该值与CompareTo实现的结果兼容。

下面的例子仅用苹果来说明这个想法。你可以用重量、体积或甜度来交换直径。这个袋子总是会返回“最近”的苹果(大小、重量或味道最相似)

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

不使用二进制搜索的解决方案(利用正在排序的列表):

public int closest(int value, int[] sorted) {
  if(value < sorted[0])
    return sorted[0];

  int i = 1;
  for( ; i < sorted.length && value > sorted[i] ; i++);

  if(i >= sorted.length)
    return sorted[sorted.length - 1];

  return Math.abs(value - sorted[i]) < Math.abs(value - sorted[i-1]) ?
         sorted[i] : sorted[i-1];
}

当然,您可以简单地使用for循环来遍历并跟踪您所使用的值和值之间的差异。它看起来更干净,但速度慢得多。

见: Finding closest match in collection of numbers

未测试

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

我认为您的答案可能是返回单个结果的最有效方法。

但是,您的方法的问题是有0(如果没有列表)、1或2个可能的解决方案。当你对一个函数有两个可能的解决方案时,你的问题就真正开始了:如果这不是最终的答案,而是一系列步骤中的第一个来确定一个最佳的操作过程,而你没有返回的答案会提供一个更好的解决方案呢?唯一正确的做法是考虑两个答案,并且只在最后比较进一步处理的结果。

把平方根函数看作是一个类似的问题。

如果您不太关心性能(考虑到该集被搜索两次),我认为使用可导航集可以得到更清晰的代码:

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

你的解似乎是渐近最优的。如果使用math.min/max,它可能会稍微快一点(尽管可能不太容易维护),一个好的JIT很可能具有使这些速度更快的内部特性。

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