数据结构中的二进制搜索和 C 中的算法分析

Question

作者在第2章(2.4.4)提到Binary_Search时提到 “

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 );
}

问：我不明白不能声明变量 unsigned.Why unsigned 限定符有问题？以及 unsigned 限定符如何将循环计数器的方向从增加变为减少？

Answer 1

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

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

对于倒计时的for循环，下面的循环永远不会结束：

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

因为i是无符号的，所以条件i >= 0将永远为真。

Answer 2

这本书的作者写错了，看来他是一个弱程序员。:)

首先，使用类型 int 作为数组的大小是个坏主意。他应该使用 size_t 类型或至少 header <stddef.h> 中定义的类型 ptrdiff_t 因为数组大小的值可以大于类型的值int可以容纳。

考虑到所有处理数组大小的 C 标准函数（例如字符串函数）都将相应的参数定义为 size_t.

类型

这里是标准函数的声明bsearch。

void *bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

nmemb 和 size 这两个参数的类型为 size_t。

问题不在于用作数组大小类型的有符号或无符号整数类型。问题是算法是如何实现的。

例如，他可以按照演示程序中所示的以下方式实现算法

#include <stdio.h>

size_t binary_search( const int a[], int x, size_t n )
{
    size_t low = 0, high = n;

    while ( low < high )
    {
        size_t middle = low + ( high - low ) / 2;

        if ( a[middle] < x )
        {
            low = middle + 1;
        }
        else if ( x < a[middle] )
        {
            high = middle;
        }
        else
        {
            return middle;
        }
    }

    return n;
}   

int main(void) 
{
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    size_t N = sizeof( a ) / sizeof( *a );

    for ( int i = -1; i <= a[N - 1] + 1; i++ )
    {
        printf( "x = %d: %zu\n", i, binary_search( a, i, N ) );
    }

    return 0;
}

程序输出为

x = -1: 10
x = 0: 0
x = 1: 1
x = 2: 2
x = 3: 3
x = 4: 4
x = 5: 5
x = 6: 6
x = 7: 7
x = 8: 8
x = 9: 9
x = 10: 10

如您所见，如果在数组中找不到值，则函数 returns 等于数组大小的索引。

通常二分查找算法returns定义目标元素索引为下界算法

这是二分查找算法的一个实现示例，returns 目标元素存在或可以插入的较低位置。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

size_t binary_search( const int a[], int x, size_t n )
{
    size_t low = 0, high = n;

    while ( low < high )
    {
        size_t middle = low + ( high - low ) / 2;

        if ( a[middle] < x )
        {
            low = middle + 1;
        }
        else
        {
            high = middle;
        }
    }

    return high;
}   

int main(void) 
{
    const size_t N = 10;
    int a[N];

    srand( ( unsigned int )time( NULL ) );

    for ( size_t i = 0; i < N; i++ )
    {
        int value = rand() % ( int )N;

        size_t n = binary_search( a, value, i );

        if ( n != i )
        {
            memmove( a + n + 1, a + n, ( i - n ) * sizeof( int ) );
        }

        a[n] = value;

        for ( size_t j = 0; j < i + 1; j++ )
        {
            printf( "%d ", a[j] );
        }
        putchar( '\n' );
    }

    return 0;
}

程序输出可能看起来像

8 
1 8 
1 5 8 
0 1 5 8 
0 1 5 5 8 
0 0 1 5 5 8 
0 0 1 2 5 5 8 
0 0 1 2 2 5 5 8 
0 0 1 2 2 5 5 8 9 
0 0 1 2 2 5 5 5 8 9

如您所见，算法的实现中没有使用任何带符号的 int 类型。

至于另一个答案中显示的循环是这样的

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

又是写错了。在这种情况下，应该使用 do-while 循环代替 for 循环，例如

unsigned i = START_VAL;
do
{
    // ...
} while ( i-- != 0 );

数据结构中的二进制搜索和 C 中的算法分析

binary search in Data Structure and Algorithm Analysis in C

c

algorithm

binary-search