Практика «Левая граница»

Скачайте проект

Во многих программах в разных контекстах можно увидеть функцию автодополнения вводимого текста. Обычно это работает так: есть словарь всех допустимых значений, и когда пользователь вводит начало некоторого слова, ему показывают несколько подходящих слов из словаря, начинающихся с букв, уже введенных пользователем.

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

Запустите проект autocomplete и поизучайте программу. В частности попробуйте набрать префиксы a, ab, zzz. На zzz поиск будет заканчиваться таймаутом.

В следующих трех заданиях нужно будет внедрить в эту программу бинарный поиск и ускорить её!

Начать нужно с простого. В файле LeftBorderTasks.cs реализуйте бинарный поиск левой границы в упорядоченном множестве фраз. Подробности в комментариях в файле LeftBorderTasks.cs!