Во многих программах в разных контекстах можно увидеть функцию автодополнения вводимого текста. Обычно это работает так: есть словарь всех допустимых значений, и когда пользователь вводит начало некоторого слова, ему показывают несколько подходящих слов из словаря, начинающихся с букв, уже введенных пользователем.
Такую функцию очень просто реализовать «в лоб», если словарь небольшой. Если же словарь большой, то необходимо задумываться об эффективности алгоритма.
Запустите проект autocomplete и поизучайте программу. В частности попробуйте набрать префиксы a, ab, zzz. На zzz поиск будет заканчиваться таймаутом.
В следующих трех заданиях нужно будет внедрить в эту программу бинарный поиск и ускорить её!
Начать нужно с простого. В файле LeftBorderTask.cs реализуйте бинарный поиск левой границы в упорядоченном множестве фраз. Подробности в комментариях в файле LeftBorderTask.cs!
|
1 2 3 4 5 6 7 |
// Вставьте сюда финальное содержимое файла LeftBorderTask.cs using System; using System.Collections.Generic; namespace Autocomplete { |
Стоимость решения этой задачи всего 100 рублей, купи решения у меня 🙂
