Алгоритм интерполяционного поиска на C++


#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;

int InterpolSearch(int massiv[], int size, int key)
{
int mid, left=0, right=size-1;
while (massiv[left]<=key && massiv[right]>=key)
{
if (massiv[right]==massiv[left])
break;
mid=left+((key-massiv[left])*(right-left))/(massiv[right]-massiv[left]);
if (massiv[mid]<key)
left=mid+1;
else if (massiv[mid]>key)
right=mid-1;
else
return mid;
}
if (massiv[left]==key)
return left;
if (massiv[right]==key)
return right;
return -1;
}

void main()
{
setlocale(LC_ALL,"Rus");
int key, i, size;
int *massiv;
cout<<"Введите размер массива"<<endl;
cin>>size;
massiv=new int [size];
cout<<"Введите поисковой запрос"<<endl;
cin>>key;
cout<<"Инициализация массива ";
for (i=0; i<size; i++)
{
massiv[i]=i+1;
cout<<massiv[i]<<" ";
}
if (InterpolSearch(massiv, size, key)==-1)
{
cout<<"Элемент не найден "<<endl;
}
else
{
cout<<"Элемент найден: "<<InterpolSearch(massiv, size, key)+1<<endl;
}
delete[] massiv;
system("pause");
}

Результат работы программы

Алгоритм интерполяционного поиска на C++

Замечание

Алгоритм интерполяционного поиска применяется для отсортированных данных.

Leave a Reply

Ваш e-mail не будет опубликован.