Рубрики

Интерполяционный поиск

Учитывая отсортированный массив из n равномерно распределенных значений arr [], напишите функцию для поиска определенного элемента x в массиве.

Линейный поиск находит элемент за время O (n), поиск перехода занимает время O (√ n), а бинарный поиск занимает время O (Log n).
Интерполяционный поиск является улучшением по сравнению с бинарным поиском для экземпляров, где значения в отсортированном массиве распределены равномерно. Двоичный поиск всегда идет к среднему элементу для проверки. С другой стороны, интерполяционный поиск может идти в разные местоположения в соответствии со значением искомого ключа. Например, если значение ключа ближе к последнему элементу, поиск по интерполяции, вероятно, начнет поиск в сторону конца.

Чтобы найти позицию для поиска, он использует следующую формулу.

// The idea of formula is to return higher value of pos
// when element to be searched is closer to arr[hi]. And
// smaller value when closer to arr[lo]
pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]

arr[] ==> Array where elements need to be searched
x     ==> Element to be searched
lo    ==> Starting index in arr[]
hi    ==> Ending index in arr[]

Алгоритм
Остальная часть алгоритма интерполяции такая же, за исключением описанной выше логики разбиения.

Шаг 1: в цикле вычислите значение «pos», используя формулу положения зонда.
Шаг 2: Если это совпадение, верните индекс элемента и выйдите.
Шаг 3: Если элемент меньше, чем arr [pos], вычислите положение зонда левого подмассива. В противном случае вычислите то же самое в правом подмассиве.
Шаг 4: Повторяйте, пока совпадение не будет найдено или подмассив не уменьшится до нуля.

Ниже приведена реализация алгоритма.

C ++

// C ++ программа для реализации интерполяционного поиска
#include<bits/stdc++.h>

using namespace std;

  
// Если x присутствует в arr [0..n-1], то возвращает
// его индекс, иначе возвращается -1.

int interpolationSearch(int arr[], int n, int x)

{

    // Находим индексы двух углов

    int lo = 0, hi = (n - 1);

  

    // Поскольку массив отсортирован, элемент присутствует

    // в массиве должен находиться в диапазоне, определенном углом

    while (lo <= hi && x >= arr[lo] && x <= arr[hi])

    {

        if (lo == hi)

        {

            if (arr[lo] == x) return lo;

            return -1;

        }

        // Зондирование позиции с сохранением

        // равномерное распределение в виду.

        int pos = lo + (((double)(hi - lo) /

            (arr[hi] - arr[lo])) * (x - arr[lo]));

  

        // Состояние цели найдено

        if (arr[pos] == x)

            return pos;

  

        // Если х больше, х в верхней части

        if (arr[pos] < x)

            lo = pos + 1;

  

        // Если х меньше, х находится в нижней части

        else

            hi = pos - 1;

    }

    return -1;

}

  
// Код драйвера

int main()

{

    // Массив элементов, по которым будет выполняться поиск

    // вестись.

    int arr[] = {10, 12, 13, 16, 18, 19, 20, 21,

                 22, 23, 24, 33, 35, 42, 47};

    int n = sizeof(arr)/sizeof(arr[0]);

  

    int x = 18; // Элемент для поиска

    int index = interpolationSearch(arr, n, x);

  

    // Если элемент был найден

    if (index != -1)

        cout << "Element found at index " << index;

    else

        cout << "Element not found.";

    return 0;

}

  
// Этот код предоставлен Мукулом Сингхом.

С

// C программа для реализации интерполяционного поиска
#include<stdio.h>

  
// Если x присутствует в arr [0..n-1], то возвращает
// его индекс, иначе возвращается -1.

int interpolationSearch(int arr[], int n, int x)

{

    // Находим индексы двух углов

    int lo = 0, hi = (n - 1);

  

    // Поскольку массив отсортирован, элемент присутствует

    // в массиве должен находиться в диапазоне, определенном углом

    while (lo <= hi && x >= arr[lo] && x <= arr[hi])

    {

        if (lo == hi){

            if (arr[lo] == x) return lo;

            return -1;

        }

        // Зондирование позиции с сохранением

        // равномерное распределение в виду.

        int pos = lo + (((double)(hi-lo) /

              (arr[hi]-arr[lo]))*(x - arr[lo]));

  

        // Состояние цели найдено

        if (arr[pos] == x)

            return pos;

  

        // Если х больше, х в верхней части

        if (arr[pos] < x)

            lo = pos + 1;

  

        // Если х меньше, х находится в нижней части

        else

            hi = pos - 1;

    }

    return -1;

}

  
// Код драйвера

int main()

{

    // Массив элементов, по которым будет выполняться поиск

    // вестись.

    int arr[] =  {10, 12, 13, 16, 18, 19, 20, 21, 22, 23,

                  24, 33, 35, 42, 47};

    int n = sizeof(arr)/sizeof(arr[0]);

  

    int x = 18; // Элемент для поиска

    int index = interpolationSearch(arr, n, x);

  

    // Если элемент был найден

    if (index != -1)

        printf("Element found at index %d", index);

    else

        printf("Element not found.");

    return 0;

}

Джава

// Java-программа для реализации интерполяционного поиска

  

class Test

{

    // Массив элементов, по которым будет выполняться поиск

    // вестись.

    static int arr[] = new int[]{10, 12, 13, 16, 18, 19, 20, 21, 22, 23,

                                         24, 33, 35, 42, 47};

      

    // Если x присутствует в arr [0..n-1], то возвращает

    // его индекс, иначе возвращается -1.

    static int interpolationSearch(int x)

    {

        // Находим индексы двух углов

        int lo = 0, hi = (arr.length - 1);

       

        // Поскольку массив отсортирован, элемент присутствует

        // в массиве должен находиться в диапазоне, определенном углом

        while (lo <= hi && x >= arr[lo] && x <= arr[hi])

        {        

  

            if (lo == hi)

            {

                if (arr[lo] == x) return lo;

                return -1;

            }

         

            // Зондирование позиции с сохранением

            // равномерное распределение в виду.

              

            int pos = lo + (((hi-lo) /

                  (arr[hi]-arr[lo]))*(x - arr[lo]));

       

            // Состояние цели найдено

            if (arr[pos] == x)

                return pos;

       

            // Если х больше, х в верхней части

            if (arr[pos] < x)

                lo = pos + 1;

       

            // Если х меньше, х находится в нижней части

            else

                hi = pos - 1;

        }

        return -1;

    }

    

    // Метод драйвера

    public static void main(String[] args) 

    {

         int x = 18; // Элемент для поиска

         int index = interpolationSearch(x);

           

         // Если элемент был найден

         if (index != -1)

               System.out.println("Element found at index " + index);

            else

               System.out.println("Element not found.");

    }

}

питон

# Программа Python для реализации интерполяционного поиска

  
# Если x присутствует в arr [0..n-1], то возвращает
# индекс этого, иначе возвращает -1

def interpolationSearch(arr, n, x):

    # Найти индексы двух углов

    lo = 0

    hi = (n - 1)

   

    # Так как массив отсортирован, элемент присутствует

    # в массиве должен быть в диапазоне, определенном углом

    while lo <= hi and x >= arr[lo] and x <= arr[hi]:

        if lo == hi:

            if arr[lo] == x: 

                return lo;

            return -1;

          

        # Зондирование позиции с сохранением

        # равномерное распределение в виду.

        pos  = lo + int(((float(hi - lo) / 

            ( arr[hi] - arr[lo])) * ( x - arr[lo])))

  

        # Состояние цели найдено

        if arr[pos] == x:

            return pos

   

        # Если х больше, х в верхней части

        if arr[pos] < x:

            lo = pos + 1;

   

        # Если х меньше, х находится в нижней части

        else:

            hi = pos - 1;

      

    return -1

  
Код водителя
# Массив объектов, поиск которых будет проводиться

arr = [10, 12, 13, 16, 18, 19, 20, 21, \

                22, 23, 24, 33, 35, 42, 47]

n = len(arr)

  

x = 18 # Элемент для поиска

index = interpolationSearch(arr, n, x)

  

if index != -1:

    print "Element found at index",index

else:

    print "Element not found"

  
# Этот код предоставлен Harshit Agrawal

C #

// C # программа для реализации
// интерполяционный поиск

using System;

  

class GFG

{

    // Массив элементов, на которых

    // поиск будет проведен.

    static int []arr = new int[]{10, 12, 13, 16, 18, 

                                 19, 20, 21, 22, 23, 

                                 24, 33, 35, 42, 47};

      

    // Если х присутствует в

    // arr [0..n-1], затем

    // возвращает его индекс,

    // иначе возвращает -1.

    static int interpolationSearch(int x)

    {

        // Найти индексы

        // два угла

        int lo = 0, hi = (arr.Length - 1);

      

        // Поскольку массив отсортирован,

        // элемент присутствует в

        // массив должен находиться в диапазоне

        // определяется углом

        while (lo <= hi && 

                x >= arr[lo] && 

                x <= arr[hi])

        {

            if (lo == hi)

            {

                if (arr[lo] == x) return lo;

                return -1;

            }

  

            // Зондирование позиции

            // с сохранением формы

            // распределение в уме.

            int pos = lo + (((hi - lo) / 

                             (arr[hi] - arr[lo])) * 

                                   (x - arr[lo]));

      

            // Состояние

            // цель найдена

            if (arr[pos] == x)

                return pos;

      

            // Если х больше, х

            // находится в верхней части

            if (arr[pos] < x)

                lo = pos + 1;

      

            // Если х меньше, х

            // находится в нижней части

            else

                hi = pos - 1;

        }

        return -1;

    }

  

    // Код драйвера

    public static void Main() 

    {

        int x = 18; // Элемент для поиска

        int index = interpolationSearch(x);

          

        // Если элемент был найден

        if (index != -1)

            Console.WriteLine("Element found " +

                                   "at index "

                                         index);

            else

            Console.WriteLine("Element not found.");

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// PHP-программа для реализации интерполяционного поиска

  
// Если x присутствует в arr [0..n-1], то возвращает
// его индекс, иначе возвращается -1.

function interpolationSearch($arr, $x, $n)

{

    // Находим индексы двух углов

    $l = 0; $h = $n - 1;

      

    // Поскольку массив отсортирован, элемент присутствует

    // в массиве должен находиться в диапазоне, определенном углом

    while ($l <= $h and $x >= $arr[$l] and

                        $x <= $arr[$h])

    {

        if ($l == $h)

        {

              if ($arr[$l] == $x) return $l;

              return -1;

        }

  

        // Зондирование позиции с сохранением

        // равномерное распределение в виду.

        $m = intval($l + (($x - $arr[$l]) * ($h - $l) / 

                               ($arr[$h] - $arr[$l])));

          

        // Состояние цели найдено

        if ($arr[$m] == $x

        {

            return $m;

        }

          

        // Если х больше, х в верхней части

        elseif ($arr[$m] < $x)

        {

            $l = $m + 1;

        

          

        // Если х меньше, х находится в нижней части

        else

        {

            $h = $m - 1;

        }

    }

      

    return -1;

}

  
// Код драйвера

  
// Массив элементов, по которым выполняется поиск
// будет проводиться.

$arr = array(10, 12, 13, 16, 18, 19, 20, 21, 

             22, 23, 24, 33, 35, 42, 47); 

$n = count($arr); 

$x = 18; // Элемент для поиска

$index = interpolationSearch($arr, $x, $n); 

  
// Если элемент был найден

if ($index != -1) 

    echo "Element found at index " . $index

else

    echo "Element not found."

  
// Этот код предоставлен Deepika Pathak
?>


Выход:

Element found at index 4


Сложность времени:
если элементы распределены равномерно, то O (log log n)) . В худшем случае это может занять до O (n).
Вспомогательное пространство: O (1)

Эта статья предоставлена Aayu sachdev . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Интерполяционный поиск

0.00 (0%) 0 votes