Это сообщение в блоге является продолжением серии сообщений об алгоритмах, поскольку мне как программисту было сложно понять эту концепцию. Почитайте первое сообщение в блоге об алгоритмах, где я представляю, что такое алгоритмы, и пример алгоритма, и второе сообщение в блоге о структурах данных, где я объяснил, что такое структуры данных и какие типы структур данных. Также ознакомьтесь с третьим сообщением в блоге о сложности времени и сложности пространства, в котором я даю объяснение сложности времени и пространства. Я также написал в блоге сообщение о Big O Notation. Недавно я написал в блоге сообщения о двоичном поиске и линейном поиске.
В этом сообщении в блоге я сосредоточусь на поиске с интерполяцией. Я объясню, что такое поиск с интерполяцией, как поиск с интерполяцией связан с алгоритмами, попытаюсь шаг за шагом разбить концепцию поиска с интерполяцией и сравнить с двоичным поиском. Я хотел потратить немного времени на изучение алгоритмов поиска, прежде чем перейти к алгоритмам сортировки.
Что такое поиск с интерполяцией?
Поиск с интерполяцией - это тип поискового алгоритма. Поиск с интерполяцией является улучшением по сравнению с двоичным поиском для сценариев, в которых значения в отсортированном массиве равномерно распределены.
Двоичный поиск переходит к среднему элементу для проверки. С другой стороны, поиск с интерполяцией может перемещаться в разные места в зависимости от значения ключа, по которому выполняется поиск. Например, если значение ключа близко к последнему элементу, поиск с интерполяцией, скорее всего, начнет поиск ближе к концу.
Поиск с интерполяцией: шаги, как это работает:
Вот подход к поиску с интерполяцией:
- В цикле вычислите значение «pos», используя формулу положения датчика (которая показана выше).
- Если есть совпадение, верните индекс элемента и выйдите.
- Если элемент меньше, чем arr [pos], вычислить положение датчика левого подмассива. В противном случае вычислите то же самое в правом подмассиве.
- Повторяйте, пока не будет найдено совпадение или пока подмассив не уменьшится до нуля.
Поиск с интерполяцией: пример
Вот пример написания алгоритма поиска с интерполяцией на основе шагов, которые я предоставил ранее. Ниже я написал функцию, которая принимает следующие параметры: массив и значение, которое я хочу найти. Функция возвращает индекс найденного значения.
А как насчет временной сложности? Если элементы распределены равномерно, то O (log log n)). В худшем случае это может занять до O (n). Поэтому для эффективной работы интерполяционного поиска элементы / данные массива должны быть отсортированы и равномерно распределены.
Общий поиск с интерполяцией - важная концепция, которую нужно понимать, когда дело касается алгоритмов. Также важно сравнить его с другими алгоритмами, такими как двоичный поиск. Спасибо, что прочитали этот пост в блоге. Теперь, когда я рассмотрел алгоритмы поиска, я рассмотрю алгоритмы сортировки в следующих публикациях в блоге.
