Interpolation Search Introduction and function / algorithm / program

Interpolation Search

"Interpolation search is an improved variant of binary search. It is also applied on the sorted list or array data structure. It compares the given item with the estimated position of element of the list/array."

"इंटरपोलेशन सर्च, बाइनरी सर्च का एक परिष्कृत रूप है। इसे बढ़ते या घटते हुए क्रम में व्यवस्थित लिस्ट या अरे डाटा स्ट्रक्चर पर लागु किया जाता है। यहाँ दिए गए आइटम की तुलना, उस आइटम की लिस्ट में अनुमानित स्थिति के एलिमेंट से की जाती है।"

In interpolation search, we first get lower bound(lb) and upper bound(ub) of given list or array and calculate mid  i.e. mid= lb+(lb-ub)*((item-list[lb])/(list[ub]-list[lb])) . 

After that we compare the item with the probing position of element of the list/array i.e.list[mid]. 

If the element is matched, then we return the location or position of that element. otherwise

If item<list[mid], then item must be exist in the lower half of the list or array so we set ub=mid-1.

If item>list[mid], then item must be exist in the upper half of the list or array so we set lb=mid+1.

This procedure will continue on the lower/upper half of the list or array until lb<=ub whenever the  lb>ub then interpolation search is called unsuccessful. 

Interpolation search is more efficient than Linear Search and Binary Search. it is very useful for searching a list with large number of elements. Its worst case time complexity is O(n) , average case time complexity is O(log log n) and space complexity is O(1).

इंटरपोलेशन सर्च में, हम सबसे पहले अरे की निम्न सीमा(lb) एवं उच्च सीमा(ub) प्राप्त करते है एवं 

mid= lb+(lb-ub)*((item-list[lb])/(list[ub]-list[lb]))  की गणना करते है।

इसके पश्चात् आइटम की तुलना, अरे के अनुमानित एलिमेंट list[mid] से करते है। यदि यह आइटम के बराबर है तब इस एलिमेंट की पोजीशन या लोकेशन प्रदान की जाती है। अन्यथा 

यदि  item<list[mid], अर्थात आइटम ज़रूर लिस्ट के पहले भाग में होगा तब ub=mid-1 सेट किया जाता है। 

यदि  item>list[mid], अर्थात आइटम ज़रूर लिस्ट के दुसरे भाग में होगा तब lb=mid+1 सेट किया जाता है।

यह प्रक्रिया लिस्ट के पहले या दुसरे भाग पर तब तक चलती रहती है जब तक कि lb<=ub होता है। जैसे ही lb>ub तब इंटरपोलेशन सर्च को असफल माना जाता है। 

इंटरपोलेशन सर्च, बाइनरी सर्च एवं लीनियर सर्च की तुलना में अधिक प्रभावी युक्ति है। यह अधिक संख्या में एलिमेंट रखने वाली लिस्ट / अरे पर लागु की जा सकती है।

इंटरपोलेशन सर्च की वर्स्ट केस टाइम कॉम्प्लेक्सिटी O(n) , एवरेज केस टाइम कॉम्प्लेक्सिटी O(log log n) एवं स्पेस कॉम्प्लेक्सिटी O(1) होती है।

Interpolation Search function / algorithm / program:-

File Name:- is.cpp

#include<iostream.h>

#include<conio.h>

#define N 5

void bs(){

int list[N],item,i,lb=0,ub=N-1,mid;

cout<<"Enter Elements of List"<<endl;

for(i=0;i<N;i++){

cout<<"Enter "<<i+1<<" element=";

cin>>list[i];

}

cout<<"Enter an Item to search=";

cin>>item;

while(lb<=ub){

mid= lb+(lb-ub)*((item-list[lb])/(list[ub]-list[lb]));

if(item==list[mid]){

cout<<item<<" is found at "<<mid<<"th index and "<<mid+1<<"th position"<<endl;

return;

}

else{

if(item>list[mid]) lb=mid+1;

else ub=mid-1;

}}

cout<<item<<" is not found"<<endl<<"Search Unsuccessful"<<endl;

return;

}

void main(){

clrscr();

cout<<"Interpolation Search"<<endl;

bs();

getch();

}

File Name:- is.c

#include<stdio.h>
#include<conio.h>
#define N 5
void is(){
int list[N],item,i,lb=0,ub=N-1,mid;
printf("Enter Elements of List\n");
for(i=0;i<N;i++){printf("Enter %d element=",i+1);
scanf("%d",&list[i]);
}
printf("Enter Item to search=");
scanf("%d",&item);
while(lb<=ub){
mid= lb+(lb-ub)*((item-list[lb])/(list[ub]-list[lb]));
if(item==list[mid]){
printf("%d is found at %d index and %d position\n",item,mid,mid+1);
return;
}
else{
if(list[mid]>item) ub=mid-1;
else
lb=mid+1;
}
}
printf("%d is not found\n Search Unsuccessful\n",item);
return;
}
void main(){
clrscr();
printf("Interpolation Search\n");
is();
getch();
}