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)?
热门推荐
1 孙媳妇祝福语简短
10 感动妈妈的祝福语简短
11 给司机老师祝福语简短
12 哥哥祝福语简短霸气句子
13 迎新祝福语简短20字
14 生日哥哥祝福语简短独特
15 道教生日祝福语简短大全
16 撩妹生日祝福语简短
17 盛夏的温馨祝福语简短
18 公司年终晚会祝福语简短