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

Question

正如上面的标题所说，我出于某种原因编写的二进制搜索函数无法找到给定的数字，如果它位于数组的末尾或开头。我曾尝试在调试器中查找问题，但没有出现任何异常情况。

例如，如果您输入 24 25 26 27 28 而它试图查找的数字是 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;
}

Answer 1

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

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

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

Binary search function can't find specified numbers if they are at the end or beginning of a sorted array

c

binary-search

cs50