Как я могу найти границы подмножества отсортированного списка?

Question

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

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

Это работает в линейном времени, однако, и мне было интересно, если кто-нибудь может предложить более эффективный способ сделать это.

Answer 1

Вы можете выполнить аналогичный двоичный поиск для верхнего элемента, за исключением того, что строка, которую вы должны искать, является первой строкой, которая начинается с префикса, строго превышающего рассматриваемый префикс. Это также занимает O (LG N) время.

Answer 2

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

Answer 3

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