#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"); }
Результат работы программы
Замечание
Алгоритм интерполяционного поиска применяется для отсортированных данных.