Поиск с интерполяцией в строках

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

Например: у нас есть массив длиной 100 с array [0] = 0 и array [99] = 99. Если мы ищем 80, интуитивно понятно попробовать array [80] вместо array [50], и если массив близок к равномерно распределенному, low + ((toFind - sortedArray [low]) * (high - low + 1)) / (sortedArray [high] - sortedArray [low]) .

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

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