Code:
#include iostream
using namespace std;
// A function to create lookup array.
void MakeDelta(int *delta, int N)
{
int power = 1, i = 0;
do
{
int half = power;
power *= 2;
delta[i] = (N+half)/power;
i++;
}while (delta[i-1] != 0);
}
// A function implementing Uniform Binary search.
int UniBinarySearch(int *a, int *del, int key)
{
int i = del[0]-1, d = 0;
flag:
// If item found at mid index return to main.
if (key == a[i])
return i;
// If lookup table vlaue is 0 then no more sub-part of array remain to search hence element not found.
else if (del[d] == 0)
return -1;
else
{
// Shift to left subpart using lookup array 'del'.
if (key < a[i])
{
i -= del[++d];
goto flag;
}
// Shift to right subpart using lookup array 'del'.
else
{
i += del[++d];
goto flag;
}
}
}
int main(void)
{
int i, n = 20,d = 0, pow = 1, index;
char ch;
int a[20] = {1, 2, 5, 8, 10, 12, 14, 15, 17, 19, 43, 65, 67, 71, 75, 79, 83, 90, 94, 99};
// Determine the size of delta array.
while(pow <= n)
{
pow *=2;
d++;
}
int del[d];
// Create lookup array.
MakeDelta(del, n);
up:
cout<<"\nEnter the Element to be searched: ";
cin>>n;
// Implement Uniform Binary search and get index value.
index = UniBinarySearch(a, del, n);
if(index == -1)
cout<<"\nItem not found";
else
cout<<"\nItem "<
// Ask user to enter choice for further searching.
cout<<"\n\n\tDo you want to search more...enter choice(y/n)?";
cin>>ch;
if(ch == 'y' || ch == 'Y')
goto up;
return 0;
}
Output:
Case 1:
Enter the Element to be searched: 19
Item 19 found at 10 position
Do you want to search more...enter choice(y/n)?y
Enter the Element to be searched: 99
Item 99 found at 20 position
Do you want to search more...enter choice(y/n)?y
Enter the Element to be searched: 94
Item 94 found at 19 position
Do you want to search more...enter choice(y/n)?y
Enter the Element to be searched: 3
Item not found
Do you want to search more...enter choice(y/n)?n
More C++ Programs:
