c - 用C进行二进制搜索

第一次在这里发帖。我最近实现了二进制搜索，但有时我的输出会返回一个巨大的负数现在我的第一个想法是打印一个数字，我的指针指向一个随机的内存位置有人能帮我解决逻辑问题吗？我该如何改进代码？

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

int binarysearch(int *array, int size, int target);

int main() {
    int array[] = { 1, 2, 3, 4, 5, 6 };
    printf("%d\n", binarysearch(array, 8, 15));
    return 0;
}

int binarysearch(int *array, int size, int target) {
    int mid;
    mid = size / 2;

    if (size < 1) {
        return -1;
    }
    if (size == 1) {
        return array[0];
    }
    if (target == array[mid]) {
        return target;
    } else
    if (target < array[mid]) {
        binarysearch(array, mid, target);
    } else{
        binarysearch(array + mid, size - mid, target);
    }
}

最佳答案

对于初学者，您使用数组中只有6个元素的无效元素数调用函数。

int array[] = { 1, 2, 3, 4, 5, 6 };
printf("%d\n", binarysearch(array, 8, 15));
                                  ^^^

还有这个片段

if (size == 1) {
    return array[0];
}

不正确第一个元素不必等于target。
本声明

    binarysearch(array + mid, size - mid, target);

必须写得像

    binarysearch(array + mid + 1, size - mid - 1, target);

最后，函数有未定义的行为，因为在这些情况下它不返回任何内容

if (target < array[mid]) {
    binarysearch(array, mid, target);
} else{
    binarysearch(array + mid, size - mid, target);
}

你得写信

if (target < array[mid]) {
    return binarysearch(array, mid, target);
} else{
    return binarysearch(array + mid, size - mid, target);
}

还有两个关于编程风格的词最好将函数命名为likebinary_search或likebinarySearch或likeBinarySearch而不是likebinarysearch。
一般来说，这不是一个好的功能设计假设数组中有一个值为-1的元素如何确定数组中是否存在此元素？
通常这样的函数返回指向目标元素的指针，以防找到它，否则返回空指针。
下面是一个演示程序，演示如何实现这种方法。

#include <stdio.h>

int * binary_search( const int *a, size_t n, int target )
{
    if ( n == 0 ) return NULL;

    size_t middle = n / 2;

    if ( a[middle] < target )
    {
        return binary_search( a + middle + 1, n - middle - 1, target );
    }
    else if ( target < a[middle] )
    {
        return binary_search( a, middle, target );
    }

    return a + middle;
}

int main(void)
{
    int array[] = { 1, 2, 3, 4, 5, 6 };
    const size_t N = sizeof( array ) / sizeof( *array );

    for ( int i = 0; i < 8; i++ )
    {
        int *target = binary_search( array, N, i  );
        if ( target )
        {
            printf( "%d is found at position %d\n",  *target, ( int )(target - array ) );
        }
        else
        {
            printf( "%d is not found\n", i );
        }
    }

    return 0;
}

程序输出是

0 is not found
1 is found at position 0
2 is found at position 1
3 is found at position 2
4 is found at position 3
5 is found at position 4
6 is found at position 5
7 is not found

根据C标准，主函数无参数应声明为

int main( void )

关于c - 用C进行二进制搜索，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40599960/