бинарный поиск с ограничением, сколько раз один объект является результатом

avatar
Philipp Bleimund
8 августа 2021 в 19:22
39
0
0

У меня есть отсортированный массив пользовательского класса. Этот класс реализует интерфейс Comparable и сортируется с помощью метода java.util.Arrays.sort(Object o).

Моя проблема в том, что я ищу в массиве через java.util.Arrays.binarySearch(Object o). Много раз. Скажем, в 1000 раз. Но я хочу ограничить, что один и тот же результирующий индекс будет только пять или десять раз в результатах.

С линейным поиском я могу сделать это легко, используя второй массив, чтобы сохранить количество использований индекса. Если он превышает заданный максимум, используется следующий лучший индекс соответствия.

Мой вопрос заключается в том, возможно ли вообще реализовать что-то подобное с бинарным поиском, не нарушая время выполнения O(log n).

Пример:
Список: [1, 2, 4, 6, 7, 8, 10]
Мой метод:

public int getBestMatchingIndex(int i, int[] array){
   int result = Arrays.binarySearch(array, i);
   if(result >= 0)
            return result;
        
   int insertionPoint = -result - 1;
   if(insertionPoint == 0)
      return insertionPoint;
   if(insertionPoint == Database.filesAndColors.length)
      return insertionPoint-1;

   return (array[insertionPoint] - i) < (i - array[insertionPoint -1]) ?
                insertionPoint : insertionPoint -1;
}

Этот метод вызывается несколько раз. Скажем, в 10 раз. Каждый раз с другим int i. Поскольку этот метод возвращает лучший индекс соответствия, может случиться так, что один индекс будет возвращен несколько раз. Потому что я хочу ограничить множественный возврат одного индекса заданным числом. При попадании в это число используется второй лучший индекс совпадения и т. д.

Заранее спасибо. А если нужен исходный код, так и скажите.

Источник
Louis Wasserman
8 августа 2021 в 19:28
0

Что значит "всего пять или десять раз в результатах"? Вы просто хотите удалить элемент после того, как он будет найден достаточно много раз?

Philipp Bleimund
8 августа 2021 в 20:14
0

@LouisWasserman Я не хочу его удалять. Я просто хочу, чтобы его нельзя было выбрать снова в результате бинарного поиска.

Louis Wasserman
9 августа 2021 в 01:02
0

Двоичный поиск обычно может выбрать только один элемент. У него действительно нет выбора.

clwhisk
9 августа 2021 в 01:16
0

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

Philipp Bleimund
9 августа 2021 в 12:04
0

@clwhisk Я предоставил более подробную версию моей проблемы. Надеюсь, это поможет.

Ответы (0)