数据结构中的二进制搜索和C中的算法分析 [英] binary search in Data Structure and Algorithm Analysis in C

问题描述

在第二章(2.4.4)中提到Binary_Search时，作者提到了"

请注意，不能将变量声明为无符号的(为什么?).在未签名的限定词有问题的地方，我们将不使用它.作为一个示例，如果无符号限定符不依赖于数组，从零开始，我们将其丢弃.我们不会使用它.作为一个例如，如果无符号限定符不依赖于数组从零开始，我们将其丢弃.我们还将避免使用for循环中作为计数器的变量的无符号类型，因为通常会增加循环计数器的方向减少，并且无符号限定符通常适用于仅前一种情况.例如，练习2.10中的代码不如果我被声明为未签名，则可以工作..

Notice that the variables cannot be declared unsigned(why?).In cases where the unsigned qualifier is questionable, we will not use it. As an example, if the unsigned qualifier is dependent on an array not beginning at zero, we will discard it. we will not use it. As an example, if the unsigned qualifier is dependent on an array not beginning at zero, we will discard it. We will also avoid using the unsigned type for variables that are counters in a for loop, because it is common to change the direction of a loop counter from increasing to decreasing and the unsigned qualifier is typically appropriate for the former case only. For example, the code in Exercise 2.10 does not work if i is declared unsigned. ".

代码如下:

int binary_search( input_type a[ ], input_type x, unsigned int n )
{
int low, mid, high; /* Can't be unsigned; why? */
/*1*/ low = 0; high = n - 1;
/*2*/ while( low <= high )
{
/*3*/ mid = (low + high)/2;
/*4*/ if( a[mid] < x )
/*5*/ low = mid + 1;
else
/*6*/ if ( a[mid] < x )
/*7*/ high = mid - 1;
else
/*8*/ return( mid ); /* found */
}
/*9*/ return( NOT_FOUND );
}

问:我不明白不能将变量声明为无符号的.为什么无符号的限定词是有问题的?以及无符号限定符如何将循环计数器的方向从增加变为减少?

Q: I can't understand that the variable cannot be declared unsigned.Why the unsigned qualifier is questionable? And how does unsigned qualifier change the direction of a loop counter from increasing to decreasing?

推荐答案

如果 mid 为0，则希望行 high = mid-1; 设置 high 到-1，这将导致循环停止.

If mid is 0, you want the line high = mid - 1; to set high to -1, which will cause the loop to stop.

如果变量是无符号的，则 high 将回绕到最大无符号值，这将导致读取超出缓冲区末尾并可能导致崩溃.

If the variables were unsigned, high would wrap around to the maximum unsigned value which would cause a read past the end of the buffer and a likely crash.

对于递减计数的循环，以下循环将永远不会结束:

As for for loops which count down, the following loop will never end:

for (unsigned i = START_VAL; i >= 0; i--) {...}  //WRONG

由于 i 是未签名的，所以条件 i> = 0 始终为真.

Because i is unsigned, the condition i >= 0 will always be true.

这篇关于数据结构中的二进制搜索和C中的算法分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！