Как искать ближайшее значение в таблице поиска? - PullRequest
5 голосов
/ 19 мая 2010

У меня есть простой одномерный массив целочисленных значений, которые представляют физический набор значений деталей, с которыми мне приходится работать. Затем я вычисляю и математически идеальное значение.

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

Массив является предопределенным и постоянным, поэтому его можно сортировать по мере необходимости.

Пример Массив поиска:

100, 152, 256, 282, 300

Поиск идеального значения 125 найдет 100 в массиве, тогда как 127 найдет 152.

Фактический массив поиска будет иметь длину около 250 элементов и никогда не изменится.

Ответы [ 5 ]

3 голосов
/ 02 октября 2012

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

Логика заключается в поиске до тех пор, пока не будет найден точный ключ или пока не останется ровно один ключ между старшим и нижним ключами при выполнении двоичного поиска.

Рассмотрим массив n [] = {1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
если вы ищете ключ: 2, то используйте алгоритм ниже
Шаг 1: высокий = 10, низкий = 0, средний = 5
Шаг 2: высокий = 5, низкий = 0, средний = 2
Шаг 3: высокий = 2, низкий = 0, мед = 1 На этом шаге будет найден точный ключ. Так что возвращается 1.

если вы ищете ключ: 3 (которого нет в массиве), используйте алгоритм ниже
Шаг 1: высокий = 10, низкий = 0, средний = 5
Шаг 2: высокий = 5, низкий = 0, средний = 2
Шаг 3: высокий = 2, низкий = 0, мед = 1
Шаг 4: высокий = 1, низкий = 0, на этом этапе высокий = низкий + 1, то есть больше нет элементов для поиска. Так что возвращается med = 1.

Надеюсь, это поможет ...

public static <T> int binarySearch(List<T> list, T key, Comparator<T> compare) {
                int low, high, med, c;
                T temp;
                high = list.size();
                low = 0;
                med = (high + low) / 2;

                while (high != low+1) {
                    temp = list.get(med);
                    c = compare.compare(temp, key);

                    if (c == 0) {
                        return med;
                    } else if (c < 0){
                        low = med;
                    }else{
                        high = med;
                    }

                    med = (high + low) / 2;
                }

                return med; 
            }

    /** ------------------------ Example -------------------- **/

    public static void main(String[] args) {
                List<Integer> nos = new ArrayList<Integer>();
                nos.addAll(Arrays.asList(new Integer[]{1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}));

                search(nos, 2); // Output Search:2  Key:1   Value:2
                search(nos, 3); // Output Search:3  Key:1   Value:2

                search(nos, 10); // Output Search:10    Key:5   Value:10
                search(nos, 11); // Output Search:11    Key:5   Value:10
            }

    public static void search(List<Integer> nos, int search){
                int key = binarySearch(nos, search, new IntComparator());
                System.out.println("Search:"+search+"\tKey:"+key+"\tValue:"+nos.get(key));
            }

            public static class IntComparator implements Comparator<Integer>{
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1.compareTo(o2);
                }
            }
3 голосов
/ 19 мая 2010

После сортировки массива используйте бинарный поиск

1 голос
/ 01 июля 2015

Алгоритм двоичного поиска из Википедии выглядит следующим образом:

int binary_search(int A[], int key, int imin, int imax)
{
  // continue searching while [imin,imax] is not empty
  while (imax >= imin)
    {
      // calculate the midpoint for roughly equal partition
      int imid = midpoint(imin, imax);
      if(A[imid] == key)
        // key found at index imid
        return imid; 
      // determine which subarray to search
      else if (A[imid] < key)
        // change min index to search upper subarray
        imin = imid + 1;
      else         
        // change max index to search lower subarray
        imax = imid - 1;
    }
  // key was not found
  return KEY_NOT_FOUND;
}

Конечное условие в случае, если ключ не найден, это то, что imax < imin.

На самом деле, это условие может найти ближайшее совпадение. Ближайшее совпадение будет лежать между imax и imin (учитывая, что любой из них может находиться за пределами массива). Обратите внимание, что imax < imin в конечном случае. Некоторые решения используют abs, чтобы найти разницу, но мы знаем, что A[imax] < key < A[imin] так:

if imax <= 0 return 0
if imin >= A.count - 1 return A.count - 1
if (key - A[imax]) < (A[imin] - key) return imax
return imin
0 голосов
/ 19 мая 2010

Python, грубая сила в несортированном списке (потому что писать Python весело) O(n):

table = (100, 152, 256, 282, 300)
value = 125

lookup_dict = dict([(abs(value-x),x) for x in table])
closest_val = ldict[min(ldict.keys())]

И правильная реализация, которая использует бинарный поиск, чтобы найти значение O(log_n):

import bisect
'''Returns the closest entry in the sorted list 'sorted' to 'value'
'''
def find_closest(sorted, value):
    if (value <= sorted[0]):
        return sorted[0]
    if (value >= sorted[-1]):
        return sorted[-1]
    insertpos = bisect.bisect(sorted, value)
    if (abs(sorted[insertpos-1] - value) <= abs(sorted[insertpos] - value)):
        return sorted[insertpos-1]
    else:
        return sorted[insertpos]
0 голосов
/ 19 мая 2010

Простое прохождение массива и вычисление abs (reference-array_value [i]) заняло бы O (N). нести индекс с наименьшей разницей.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...