균일한 이진 검색을 수행하는 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)?