โปรแกรม 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)?