代码之家 › 专栏 › 技术社区 › user8742308

如果指定的数字位于排序数组的末尾或开头,则二进制搜索函数无法找到它们

cs50 binary-search c

1

user8742308 · 技术社区 · 8 年前

例如,如果您输入 24 25 26 27 28 return false .

但是如果数字是 24 25 28 26 30 会的 return true

bool search(int value, int values[], int n)
{
    // check if only 1 item exists in values and if it is the item which is being looked for
    if (n == 1)
    {
        if (value == values[0]) return true;
        else return false;
    }
    int middle = n / 2;

    // if the value is greater than middle, search the right half of the array
    if (value > values[middle])
    {
        // initialize rightHalf since it is a variable length array
        int rightHalf[n];
        for(int x = 0; x <= n; x++) rightHalf[x] = 0;

        int rightHalfSize = n - middle;

        if (value > values[middle])
        {
            int rightHalfSize = n - middle - 1;
            for (int i = 0, m = middle + 1; i < rightHalfSize; i++, m++)
            {
                rightHalf[i] = values[m];
            }
        }
    return search(value, rightHalf, rightHalfSize);
  } // if the value is less than middle, search the left half of the array
    else if (value < values[middle])
    {
        // initialize leftHalf since it is a variable length array
        int leftHalf[n];
        for(int y = 0; y <= n; y++) leftHalf[y] = 0;

        int leftHalfSize = n - middle;

        for (int i = 0, m = 0; i < middle; i++, m++)
        {
            leftHalf[i] = values[m];
        }
    return search(value, leftHalf, leftHalfSize);
  }
    else if (value == values[middle]) return true;

  return false;
}

1 回复 | 直到 8 年前

1

Vlad from Moscow 8 年前

目前尚不清楚在函数内创建可变长度数组的目的,该数组至少由于循环而导致未定义的行为

int rightHalf[n];
for(int x = 0; x <= n; x++) rightHalf[x] = 0;

因为有人试图改变数组之外的内存,使x等于n。

例如

#include <stdio.h>
#include <stdbool.h>

bool search( const int a[], size_t n, int value )
{
    if ( !n )
    {
        return false;
    }
    else
    {
        size_t middle = n / 2;
        if ( a[middle] < value )
        {
            return search( a + middle + 1, n - middle - 1, value );
        }
        else if ( value < a[middle] )
        {
            return search( a, middle, value );
        }
        else 
        {
            return true;
        }
    }
}

int main(void) 
{
    int a[] = { 24, 25, 26, 27, 28 };
    const size_t N = sizeof( a ) / sizeof( *a );

    printf( "a[0] - 1 is found - %d\n", search( a, N, a[0] - 1 ) );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "a[%zu] is found - %d\n", i, search( a, N, a[i] ) );

    }

    printf( "a[%zu] + 1 is found - %d\n", N - 1, search( a, N, a[N-1] + 1 ) );

    return 0;
}

程序输出为

a[0] - 1 is found - 0
a[0] is found - 1
a[1] is found - 1
a[2] is found - 1
a[3] is found - 1
a[4] is found - 1
a[4] + 1 is found - 0