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

Например: у нас есть массив длиной 100 с массивом [0] = 0 и массивом [99] = 99. Если мы ищем 80, интуитивно попробовать использовать массив [80] вместо массива [50], и если массив близок к равномерно распределенному, ожидаемое время выполнения сокращается доlog(log(N))

Для чисел местоположение для проверки определяется уравнением:low + ((toFind - sortedArray[low]) * (high - low + 1)) / (sortedArray[high] - sortedArray[low]).

Типичный пример, используемый для демонстрации интуитивного характера интерполяционного поиска: представьте, что вы пытаетесь найти слово «желтый» в словаре. Вы бы не использовали бинарный поиск и не пошли бы на полпути. Скорее вы бы отправились в ожидаемое место.

Люди могут, естественно, линейно интерполировать строки, но я не могу понять, как их кодировать. Как мы линейно интерполируем строки?