C++ प्रोग्राम यूनिफ़ॉर्म बाइनरी सर्च करने के लिए

यूनिफ़ॉर्म बाइनरी सर्च में यहां हम लुकअप टेबल का उपयोग करके बाइनरी सर्च को लागू करते हैं। यह द्विआधारी खोज में एक सुधार है क्योंकि टेबल लुकअप एक बदलाव और जोड़ से तेज है। इस दृष्टिकोण की समय जटिलता O(log(n)) है।

एल्गोरिदम

Begin
   Assign the data to the array in a sorted manner.
   Calculate the maximum length of lookup array and declare a new array ‘del’.
   Assign the values to the lookup array as n/2, n/4 and so on till ‘0’, where n is the length of the data
   array.
   Call UniBinarySearch() function.
   Assign mid to the value at ‘0’ index of ‘dl’ array and compare key to the value at mid index.
   If key is equal then return the index value to the main.
   If index value in ‘dal’ is zero then the element is not there, return - 1 to main.
   If it is lesser, subtract next value stored in ‘dal’ array and shift the pointer to next value in ‘dal’
   array.
   If it is greater, add next value stored in ‘dal’ array and shift the pointer to next value in ‘dal’ array.
   print the index value returned by the function and ask for user’s choice to search more.
End

उदाहरण कोड

#include<iostream>
using namespace std;
void lookUpArray(int *a, int N) {
   int power = 1, i = 0;
   do {
      int half = power;
      power *= 2;
      a[i] = (N+half)/power;
      i++;
   } while (a[i-1] != 0);
}
int UniBinarySearch(int *a, int *dal, int key) {
   int i = d[0]-1, d = 0;
   flag:
   if (key == a[i])
      return i;
   else if (dal[d] == 0)
      return -1;
   else {
      if (key < a[i]) {
         i -= dal[++d];
         goto flag;
      }
      else {
         i += dal[++d];
         goto flag;
      }
   }
}
int main(void) {
   int i, n = 10, d = 0, pow = 1, index;
   char ch;
   int a[10] = {2,6,7, 10, 12, 14, 12, 16,20, 26};
   while(pow <= n) {
      pow *=2;
      d++;
   }
   int del[d];
   lookUpArray(d, n);
   up:
   cout<<"\nEnter the Element to be searched: ";
   cin>>n;
   index = UniBinarySearch(a, del, n);
   if (index == -1)
      cout<<"\nItem not found";
   else
      cout<<"\nItem "<<n<<" found at "<<index+1<<" position";
      cout<<"\n\n\tDo you want to search more...enter choice(y/n)?";
     cin>>ch;
   if(ch == 'y' || ch == 'Y')
      goto up;
   return 0;
}

आउटपुट

Enter the Element to be searched: 7
Item 7 found at 3 position
Do you want to search more...enter choice(y/n)?y
Enter the Element to be searched: 21
Item not found
Do you want to search more...enter choice(y/n)?