Алгоритм приближенного поиска в отсортированном целочисленном списке

Question

Рассмотрим массив целых чисел (предполагается, что они отсортированы); Я хотел бы найти индекс массива целого числа, который является ближайшим к данному целому числу самым быстрым возможным способом. И в случае, когда существует несколько возможностей, алгоритм должен идентифицировать все.

Пример: рассмотрим T = (3, 5, 24, 65, 67, 87, 129, 147, 166), и если данное целое число равно 144, то код должен идентифицировать 147 как ближайшее целое число, и дать индекс массива 7, соответствующий этой записи. Для случая 66 алгоритм должен идентифицировать 65 и 67.

Существуют ли O (1) или хотя бы O (log N) алгоритмы для этого? Реализация алгоритма прямого поиска (бинарный поиск, поиск по дереву, хеширование и т. Д.) Не будет работать, так как для этого потребуется идеальное соответствие. Есть ли способ, которым они могут быть изменены для обработки приблизительного поиска?

Я разрабатываю код на Си.

Спасибо

Answer 1

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

Answer 2

Правильно реализованный binary-search должен сделать свое дело - до тех пор, пока вы определите момент, когда диапазон поиска сократился только до двух элементов. Тогда вы просто выбираете ближайший. Сложность: O (log n).