Найти ближайшее значение в упорядоченном списке

Мне интересно, как бы вы написали простой Java-метод поиска целочисленного шкафа для данного значения в отсортированном списке целых чисел.

Вот моя первая попытка:

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

Что вы думаете об этом решении? Я уверен, что есть более чистый способ сделать эту работу.

Может быть, такой метод существует где-то в библиотеках Java, и я пропустил его?

Ответ 1

попробуйте этот небольшой метод:

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

Ответ 2

Я думаю, что у вас есть самый простой и эффективный способ сделать это. Поиск "ближайшего" элемента в отсортированном списке не является чем-то, что обычно встречается при программировании (обычно вы ищете тот, который больше, или тот, который меньше). Проблема имеет смысл только для числовых типов, поэтому она не очень обобщаема, и поэтому было бы необычно иметь библиотечную функцию для нее.

Ответ 3

Чтобы решить эту проблему, я бы распространил Comparable Interface на метод 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;
   }
}

Ответ 4

Решение без бинарного поиска (использует сортировку списка):

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

Ответ 5

Конечно, вы можете просто использовать цикл for, чтобы пройти через и отслеживать разницу между значением, в котором вы находитесь, и значением. Это выглядело бы чище, но было бы намного медленнее.

Смотрите: Поиск ближайшего соответствия в коллекции чисел

Ответ 6

Не тестировалось

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

Ответ 7

Я думаю, что ваш ответ, вероятно, самый эффективный способ вернуть единственный результат.

Однако проблема с вашим подходом заключается в том, что существует 0 (если нет списка), 1 или 2 возможных решения. Это когда у вас есть два возможных решения для функции, которые действительно возникают ваши проблемы: что, если это не окончательный ответ, а только первый из нескольких шагов для определения оптимального курса действий и ответ, который вы не сделали возвращение обеспечило бы лучшее решение? Единственное, что нужно сделать, это рассмотреть оба ответа и сравнить результаты дальнейшей обработки только в конце.

Подумайте о функции квадратного корня как о некоторой аналогичной проблеме.

Ответ 8

Если вы не серьезно относитесь к производительности (при условии, что поиск выполняется дважды), я думаю, что использование набора Navigable приводит к более четкому коду:

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

Ответ 9

Ваше решение кажется асимптотически оптимальным. Он может быть немного быстрее (хотя, вероятно, менее обслуживаемым), если он использует 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);
}