Интерполяционный поиск по строкам
Для тех из вас, кто не знаком с интерполяционным поиском, это метод поиска значения в отсортированном массиве, который потенциально быстрее двоичного поиска. Вы смотрите на первый и последний элемент и (при условии, что содержимое массива распределено равномерно) линейно интерполируются, чтобы предсказать местоположение.
Например: у нас есть массив длиной 100 с массивом [0] = 0 и массивом [99] = 99. Если мы ищем 80, интуитивно попробовать использовать массив [80] вместо массива [50], и если массив близок к равномерно распределенному, ожидаемое время выполнения сокращается доlog(log(N))
Для чисел местоположение для проверки определяется уравнением:low + ((toFind - sortedArray[low]) * (high - low + 1)) / (sortedArray[high] - sortedArray[low])
.
Типичный пример, используемый для демонстрации интуитивного характера интерполяционного поиска: представьте, что вы пытаетесь найти слово «желтый» в словаре. Вы бы не использовали бинарный поиск и не пошли бы на полпути. Скорее вы бы отправились в ожидаемое место.
Люди могут, естественно, линейно интерполировать строки, но я не могу понять, как их кодировать. Как мы линейно интерполируем строки?