Chương trình C ++ để thực hiện tìm kiếm nhị phân thống nhất

Trong tìm kiếm nhị phân thống nhất ở đây chúng tôi thực hiện tìm kiếm nhị phân bằng cách sử dụng bảng tra cứu. Đây là một cải tiến trong tìm kiếm nhị phân vì tra cứu bảng nhanh hơn so với việc thay đổi và bổ sung. Độ phức tạp về thời gian của phương pháp này là O (log (n)).

Thuật toá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

Mã mẫu

#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;
}

Đầu ra

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)?