सी ++ प्रोग्राम इंटरपोलेशन सर्च एल्गोरिदम लागू करने के लिए

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

प्रक्षेपण खोज तकनीक की जटिलता

• समय जटिलता:O(लॉग<उप>2 (लॉग<उप>2 n)) औसत मामले के लिए, और O(n) सबसे खराब स्थिति के लिए (जब वस्तुओं को तेजी से वितरित किया जाता है)

• अंतरिक्ष जटिलता:ओ(1)

Input − A sorted list of data
10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995. 
The search key 780
Output − Item found at location: 16

एल्गोरिदम

प्रक्षेप खोज (सरणी, प्रारंभ, अंत, कुंजी)

इनपुट :एक क्रमबद्ध सरणी, प्रारंभ और समाप्ति स्थान, और खोज कुंजी

आउटपुट :कुंजी का स्थान (यदि पाया जाता है), अन्यथा गलत स्थान।

Begin
   while start <= end AND key >= array[start] AND key <= array[end] do
      dist := key – array[start]
      valRange := array[end] – array[start]
      fraction := dist / valRange
      indexRange := end – start
      estimate := start + (fraction * indexRange)
      if array[estimate] = key then
         return estimate position
      if array[estimate] < key then
         start := estimate + 1
      else
         end = estimate -1
   done
   return invalid position
End

उदाहरण कोड

#include<iostream>
using namespace std;
int interpolationSearch(int array[], int start, int end, int key) {
   int dist, valRange, indexRange, estimate;
   float fraction;
   while(start <= end && key >= array[start] && key <= array[end]) {
      dist = key - array[start];
      valRange = array[end] - array[start];     //range of value
      fraction = dist / valRange;
      indexRange = end - start;
      estimate = start + (fraction * indexRange);      //estimated position of the key
      if(array[estimate] == key)
         return estimate;
      if(array[estimate] < key)
         start = estimate +1;
      else
         end = estimate - 1;
   }
   return -1;
}
int main() {
   int n, searchKey, loc;
   cout << "Enter number of items: ";
   cin >> n;
   int arr[n];      //create an array of size n
   cout << "Enter items: " << endl;
   for(int i = 0; i< n; i++) {
      cin >> arr[i];
   }
   cout << "Enter search key to search in the list: ";
   cin >> searchKey;
   if((loc = interpolationSearch(arr, 0, n-1, searchKey)) >= 0)
      cout << "Item found at location: " << loc << endl;
   else
      cout << "Item is not found in the list." << endl;
}

आउटपुट

Enter number of items: 20
Enter items:
10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956
995
Enter search key to search in the list: 780
Item found at location: 16