You get a bonus - 1 coin for daily activity. Now you have 1 coin

Интерполяционный (интерполирующий ) поиск с предсказанием местонахождения элемента

Lecture



The interpolation search is based on the interpolation operation. Interpolation - finding intermediate values ​​of a value over an existing discrete set of known values. Interpolation search only works with ordered arrays; it is similar to binary, in the sense that at each step a certain search area is computed, which, as the algorithm runs, narrows down. But unlike binary, interpolation search does not divide the sequence into two equal parts, but calculates the approximate location of the key (the desired element), focusing on the distance between the desired and the current value of the element. The idea of ​​the algorithm resembles the search for a phone number in the usual directory that is well known to older generations: the list of caller names is ordered, so it’s not difficult to find the desired phone number, since, for example, we are looking for a subscriber with a last name starting with the letter “U”, then Further search will be reasonable to go to the end of the directory.

The formula that determines the interpolation search algorithm is as follows:

Интерполяционный (интерполирующий ) поиск с предсказанием местонахождения элемента

Here mid is the element number with which the key value is compared, key is the key (the desired element), A is an array of ordered elements, left and right are numbers of extreme elements of the search area. It is important to note that the division operation in the formula is strictly integer, that is, the fractional part, whatever it is, is discarded.

C ++ program code:

one
2
3
four
five
6
7
eight
9
ten
eleven
12
13
14
15
sixteen
17
18
nineteen
20
21
22
23
24
25
26
27
28
29
thirty
31
#include "stdafx.h"
#include
using namespace std;
const int N = 17;
// interpolation search
int InterpolSearch (int A [], int key)
{
int mid, left = 0, right = N-1;
while (a [left] <= key && a [right]> = key)
{
mid = left + ((key-A [left]) * (right-left)) / (A [right] -A [left]);
if (A [mid] else if (A [mid]> key) right = mid-1;
else return mid;
}
if (A [left] == ​​key) return left;
else return -1;
}
// main function
void main ()
{
setlocale (LC_ALL, "Rus");
int i, key;
int A [N] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
cout << "Search Item>"; cin >> key; // enter key
cout << "Source array:";
for (i = 0; i if (InterpolSearch (A, key) == - 1) cout << "\ nItem is not found";
else cout << "\ nItem number:" << InterpolSearch (A, key) +1;
system ("pause >> void");
}

Pascal program code:

one
2
3
four
five
6
7
eight
9
ten
eleven
12
13
14
15
sixteen
17
18
nineteen
20
21
22
23
24
25
26
27
28
29
program InterpolationSearch;
uses crt;
const N = 17;
type Arr = array [1..N] of integer;
var mid, left, right, key, i: integer;
const A: Arr = (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59);
{interpolation search}
function InterpolSearch (A: Arr; key: integer): integer;
begin
left: = 1; right: = N;
while ((A [left] <= key) and (A [right]> = key)) do
begin
mid: = left + ((key-A [left]) * (right-left)) div (A [right] -A [left]);
if (A [mid] else if (A [mid]> key) then right: = mid-1
else begin InterpolSearch: = mid; exit; end;
end;
if (A [left] = key) then InterpolSearch: = left
else InterpolSearch: = - 1;
end;
{main program block}
begin
write ('search element>'); read (key); {key entry}
write ('Source array:');
for i: = 1 to N do write (A [i], ''); {array output}
writeln;
if (InterpolSearch (A, key) = - 1) then write ('Element not found')
else write ('Element number:', InterpolSearch (A, key));
end.

Interpolation search in efficiency, as a rule, exceeds the binary one, on average requiring log (log (N)) operations. Thus, the time of his work is O (log (log (N))). But if, for example, the sequence increases exponentially, then the speed will increase to O (N), where N (as in the previous case) is the total number of items in the list. The algorithm shows the highest performance on a sequence whose elements are evenly distributed relative to each other.

Java:

Интерполяционный (интерполирующий ) поиск с предсказанием местонахождения элемента

Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Algorithms

Terms: Algorithms