5

Имеется большой отсортированный массив строк (100000 строк, каждая строка может иметь длину в 32 символа (латинские буквы и цифры)).
Вводим начало нужной нам строки.
Как реализовать максимально быстрый поиск нужной строки?

Как произвести индексацию строк, ведь пользователь может ввести и одну букву, и две, и пятнадцать, а доступно памяти только 64 MB?

18
  • 3
    Можно бинарным поиском, раз массив отсортирован (я так понял по алфавиту). Сначала ищешь ту половину, где есть строки, начинающиеся с первой буквы из строки, введенной пользователем. Затем, как наткнулся на такое слово (то есть отрезал все половины, где нет слов, начинающихся с этой буквы). Затем добавляешь вторую букву и ищешь тем же алгоритмом уже по две буквы и так пока не найдешь. Ну это алгоритм, который просто в мыслях пришел... Самый быстрый поиск в отсортированном массиве - бинарный. 18 мая 2017 в 7:44
  • 2
    100к строк - бинарно это 17 поисков (сравнений), быстрее вряд ли получится.
    – Akina
    18 мая 2017 в 7:50
  • 1
    @Lugovets Ну можно строить дерево, при каждом поиске дополнять его. Но ограничение по памяти может помешать. Надо проверять. В идеале можно попытаться еще до выполнения поиска, сразу после заполнения массива, построить дерево, но надо вычислять опять же потребляемую память. 18 мая 2017 в 7:55
  • 1
    17 поисков на первую букву, а если букв 25 Ну можете построить индексный массив для первой буквы (или первых двух) и выбирать границы поиска одним индексным обращением - выиграете в среднем 4 поиска.
    – Akina
    18 мая 2017 в 8:02
  • 2
    @Lugovets, если букв 25 в худшем случае будет 25 * 17 = 425 операций. Это же ничтожно мало.
    – iksuy
    18 мая 2017 в 8:03

1 ответ 1

1

Зачем что-то реализовывать если все уже реализовано до нас в java.utils.Arrays))

public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) пихаешь туда свой массив, даешь слово которое хочешь найти и для стринга можно компаратор указать null, тогда поиск будет просто юзать Comparable реализованный в String.

Arrays.binarySearch(textArray, "or", null);

Если ключ не найден выдаст отрицательный индекс

2
  • А если нужно первую с таким префиксом?
    – Qwertiy
    25 июн 2019 в 16:32
  • по документации binarySearch возвращает -1, если элемент не найден. 5 сен 2020 в 18:48

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.