均一二分探索を実行する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)?