如何实现动态二进制搜索n个元素的搜索和INSERT操作 [英] How to implement dynamic binary search for search and insert operations of n element
问题描述
的想法是使用多个阵列，每个长度为2 ^ k的，用于存储n个元素，根据n.Each阵列的二进制重新presentation是排序和不同阵列不以任何方式排列。
在上述数据结构中，搜索是通过每个阵列上二进制搜索的序列。 插入是通过相同长度的阵列的合并的一个序列，直到一个空数组为止。
详细资料：让我们假设有长度为2 ^ k的垂直阵列和该阵列中的每个节点有附加长度的水平阵列2 ^氏/ P>
即，为了垂直阵列的第一个节点，长度的水平阵列2 ^ 0 = 1连接，以垂直阵列的第二节点，长度的水平阵列2 ^ 1 = 2连接等。所以所述插入首先执行第一水平阵列中，对于第二插入件的第一阵列变空和第二水平数组满带2的元素，所述第三插入件第一和第二阵列HORIZ。阵列填充等。 我执行正常的二进制搜索的搜索和插入如下：
INT主要（）
{
诠释一个[20] = {0};
诠释N，I，J，温度;
INT *求，*年底，*中旬，目标;
的printf（请输入你想要进入总整数（使其低于20）：\ N）;
scanf函数（％d个，和放大器; N）;
如果（N＆GT; = 20）返回0;
的printf（请输入整数数组元素：\ N）;
对于（I = 0; I＆n种;我+ +）
{
scanf函数（％d个，和放大器; A [1]）;
}
//排序加载的阵列，二进制搜索！
对于（I = 0; I＆n种-1;我+ +）
{
为（J = 0; J＆n种-I-1; J ++）
{
如果（一[J + 1]; A [J]。）
{
TEMP = A [J]。
一个[J] =一[J + 1];
一[J + 1] =气温;
}
}
}
的printf（排序的数字是：）;
对于（I = 0; I＆n种;我+ +）
{
的printf（％D，A [1]）;
}
//指向开始和结束的阵列的
BEG =＆放大器;一个[0];
结束=＆放大器;一个[N]; //使用N =过去装载的数组的一个元素！
//中间应该在这些地址的中间某处指向
中期=乞+ = N / 2;
的printf（\ñ输入数字要搜索：）;
scanf函数（％d个，和放大器;目标）;
//二进制搜索中，有一个与在而中间（）！
而（（BEG＆LT; =结束）及和放大器;！（* =中期目标））
{
//处于较低或上半部分的目标是什么？
如果（目标＆LT; *中旬）
{
结束=中旬 - 1; //新的结束
N = N / 2;
中期=乞+ = N / 2; //新中间
}
其他
{
BEG =中等+ 1; // 新的开始
N = N / 2;
中期=乞+ = N / 2; //新中间
}
}
//找到目标？
如果（* ==中期目标）
{
的printf（\ N％d个！，目标）;
}
其他
{
的printf（\ N％D不存在！，目标）;
}
的getchar（）; //陷阱进入
的getchar（）; // 等待
返回0;
}
任何人都可以请建议如何修改此程序或新的方案，以实现动态二进制搜索的工作原理如上解释！
动态二进制搜索确实是一个很酷的算法。它的参考算法导论（Cormen，Leiserson和维斯特）问题18-2和它密切相关的在线归并（克努特TAOCP前5.2.4-17）。它为O（log（n））的平均成功的搜索时间。最坏情况下，成功的和不成功的搜索都为O（log 2 （N））。而且更容易code比平衡查找树。
搜索是相当简单的，你只需要搜索的每一行，直到你找到的东西（开始最大）。我实现了下面的插入。合并程序完成所有的排序。请注意，每一行是一个int *这是一样的整数（或空）的数组。如果我是在高性能的版本，我会考虑缓存一些较小尺寸的数组作为malloc和free往往是缓慢的。
INT *行[30];
INT LASTROW = 0;
无效dbs_insert（INT V）;
INT * dbs_merge（INT *一，为int * B，INT LEN）;
无效dbs_insert（INT V）{
INT * NEW_ROW;
INT I;
NEW_ROW =的malloc（的sizeof（INT））;
NEW_ROW [0] = v的
I = 0;
而（行[I]！= NULL）{
NEW_ROW = dbs_merge（行[I]中，NEW_ROW，1所述;＆其中;一）;
行[I] = NULL;
我++;
}
行[I] = NEW_ROW;
如果（I> LASTROW）LASTROW =我;
}
INT * dbs_merge（INT *一，为int * B，INT LEN）{
INT AI = 0;
INT BI = 0;
INT CI = 0;
INT * C;
C =的malloc（（2 * LEN）*的sizeof（INT））;
而（AI＆LT; LEN && BI＆LT; LEN）{
如果（A [爱]＆LT; = B [BI]）{
C [CI +] = A [艾++];
} 其他 {
C [CI +] = B [双++];
}
}
而（AI＆LT; LEN）
C [CI +] = A [艾++];
而（BI＆LT; LEN）
C [CI +] = B [双++];
免费（一）;
免费（二）;
返回℃;
}
The idea is to use multiple arrays, each of length 2^k, to store n elements, according to binary representation of n.Each array is sorted and different arrays are not ordered in any way.
In the above mentioned data structure, SEARCH is carried out by a sequence of binary search on each array. INSERT is carried out by a sequence of merge of arrays of the same length until an empty array is reached.
More Detail: Lets suppose we have a vertical array of length 2^k and to each node of that array there attached horizontal array of length 2^k.
That is, to the first node of vertical array, a horizontal array of length 2^0=1 is connected,to the second node of vertical array, a horizontal array of length 2^1= 2 is connected and so on. So the insert is first carried out in the first horizontal array, for the second insert the first array becomes empty and second horizontal array is full with 2 elements, for the third insert 1st and 2nd array horiz. array are filled and so on. I implemented the normal binary search for search and insert as follows:
int main()
{
int a[20]= {0};
int n, i, j, temp;
int *beg, *end, *mid, target;
printf(" enter the total integers you want to enter (make it less then 20):\n");
scanf("%d", &n);
if (n >= 20) return 0;
printf(" enter the integer array elements:\n" );
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
// sort the loaded array, binary search!
for(i = 0; i < n-1; i++)
{
for(j = 0; j < n-i-1; j++)
{
if (a[j+1] < a[j])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
printf(" the sorted numbers are:");
for(i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
// point to beginning and end of the array
beg = &a[0];
end = &a[n]; // use n = one element past the loaded array!
// mid should point somewhere in the middle of these addresses
mid = beg += n/2;
printf("\n enter the number to be searched:");
scanf("%d",&target);
// binary search, there is an AND in the middle of while()!!!
while((beg <= end) && (*mid != target))
{
// is the target in lower or upper half?
if (target < *mid)
{
end = mid - 1; // new end
n = n/2;
mid = beg += n/2; // new middle
}
else
{
beg = mid + 1; // new beginning
n = n/2;
mid = beg += n/2; // new middle
}
}
// find the target?
if (*mid == target)
{
printf("\n %d found!", target);
}
else
{
printf("\n %d not found!", target);
}
getchar(); // trap enter
getchar(); // wait
return 0;
}
Could anyone please suggest how to modify this program or a new program to implement dynamic binary search that works as explained above!!
Dynamic binary search really is a cool algorithm. The reference for it is Introduction to Algorithms (Cormen, Leiserson and Rivest) problem 18-2 and it is closely related to the online mergesort (Knuth TAOCP ex 5.2.4-17). It has O(log(n)) average successful search time. Worst case succesful and unsuccesful search are both O(log2(n)). And is much easier to code than balanced search trees.
The search is fairly straight forward, you just have to search each row until you find something (start at the biggest). I've implemented an insertion below. The merge routine does all the sorting. Note that each row is an int * which is the same as an array of ints (or NULL). If I was making a high performance version, I'd look into caching some smaller sized arrays as malloc and free tend to be slow.
int *row[30];
int lastrow=0;
void dbs_insert(int v);
int *dbs_merge(int *a, int *b, int len);
void dbs_insert(int v) {
int *new_row;
int i;
new_row=malloc(sizeof(int));
new_row[0]=v;
i=0;
while (row[i]!=NULL) {
new_row=dbs_merge(row[i],new_row,1<<i);
row[i]=NULL;
i++;
}
row[i]=new_row;
if (i>lastrow) lastrow=i;
}
int *dbs_merge(int *a, int *b, int len) {
int ai=0;
int bi=0;
int ci=0;
int *c;
c=malloc((2*len)*sizeof(int));
while (ai <len && bi < len) {
if (a[ai]<=b[bi]) {
c[ci++]=a[ai++];
} else {
c[ci++]=b[bi++];
}
}
while (ai<len)
c[ci++]=a[ai++];
while (bi<len)
c[ci++]=b[bi++];
free(a);
free(b);
return c;
}
这篇关于如何实现动态二进制搜索n个元素的搜索和INSERT操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
