# 如何實現n元素的搜索和插入操作的動態二進制搜索

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.

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
{
}

getchar(); //trap enter
getchar(); //wait
return 0;
}


## 最佳答案

row 0: array[0] #
row 1: array[1] # #
row 2: array[3] # # # #
row 3: array[7] # # # # # # # #


1。外部二進制搜索

2。行二進制搜索

## 外部二進制搜索

  [Equation 1] index = power(2, row #) - 1


[Equation 2} midpoint = ((highest - lowest)/2) + lowest


   row_midpoint = ((row_highest + row_lowest)/2) + row_lowest


array_midpoint_index = (1 << row_midpoint) - 1


## 行二進制搜索

Details are left as an exercise for the reader.
(BTW, making pictures and diagrams is always a helpful practice when getting stuck on a problem, whether it be computer algorithms or physic's word problems.)