Бинарный поиск в php над списком строк

Question

У меня есть файл, содержащий имена песен 30K. Я должен использовать этот список для автоматического предложения текста с помощью AJAX. Некоторые имена также начинаются с цифр. Мой вопрос: могу ли я выполнить бинарный поиск по этому списку? Если да, то как?

Answer 1

Прежде всего рода перечень;

Предположим, что первая буква, которую пользователь набрал, - «A»;

Начать с high = 0 и low = количество строк -1;

Затем вы можете определить высокий и индекс низкой, где высокий последний индекс, который начинается с «A» и низкий первый индекс, который имеет строку начинается с «A». С двумя бинарными поисками это может быть достигнуто.

Таким образом, если следующая буква, набравшая букву «B», вы делаете другой бинарный поиск в диапазоне высоких и низких значений выше и снова корректируете высокий и низкий уровни с помощью двух бинарных поисков. Убедитесь, что вы ищите второй символ строк между высоким и низким для соответствия «B» и т. Д. :)

Примечание: Я бы предложил использовать базу данных, чтобы сделать это, но по мере того, как вы спрашивали, есть ли каким-либо образом использовать бинарный поиск, Я отвечаю на этот путь :)

Простой SQL-запрос: SELECT column_name FROM table_name WHERE column_name LIKE 'prefix%' для выбора строки те начинаются с «префикса» хранится в столбце «column_name» таблицы «table_name»

Answer 2

Вы можете использовать mixed array_search (mixed $needle , array $haystack [, bool $strict = false ])

php.net documentation