从 C 中的递归二进制搜索返回布尔值

Question

我正在尝试在 C 中实现递归二进制搜索。我正在使用 CS50 库将 bool 定义为一种类型。我的代码将在测试数组中找到输入的值。但是，当我使用 if 语句检查返回值 r 时，它通常返回 false，即使数字是 found.My 代码如下：

#include <stdio.h>
#include <cs50.h>

bool binarysearch(int value, int values [], int n, int lo, int hi);
int main(void)
{
    // test array of 6 values sorted.
    int values[] = {1 , 2, 3, 4 , 5, 6};
    int n = 6;
    int hi = values[n-1];
    int lo = values[0];
    // input from user
    printf("What number\n");
    int value = GetInt();
    //search for value in test arary
    bool r = binarysearch(value,values,n,lo,hi);
    if (!r)
    {
        printf("not right\n");
        return 1;
    }
    return 0;
}

bool binarysearch(int value, int values [], int n, int lo, int hi)
{
    int mid;
    mid = (lo + hi)/2;
    // condition to avoid indexing error
    if (((mid == 0) || (mid == n-1)) && (values[mid] != value) )
    {
        return false;
    }
    //check if value is at mid index in test array
    if (values[mid] == value)
    {
        printf("Key Found\n");
        return true;
    }
    // check right half of array
    else if(value > values[mid])
    {
        binarysearch(value, values,n, mid+1, hi);
    }
    //  check left half of array
    else if(value <values[mid])
    {
        binarysearch(value, values,n,lo, mid-1);
    }
    return false;
}

Answer 1

此示例将执行二进制搜索和 return 布尔值，类似于您的代码，但算法必须正确。

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

bool binarysearch(int value, int values[], int n, int lo, int hi) {
    int mid = (hi + lo) / 2;
    if (lo <= hi) {
        if (values[mid] == value) {
            printf("Key found at index %d \n", mid);
            return true;
        }
        else if (values[mid] > value)
            return binarysearch(value, values, n, lo, mid);
        else
            return binarysearch(value, values, n, mid + 1, hi);;
    }
    else return 0;
}

main() {
    int i, n, value;
    int values[] = {1, 2, 3, 4, 5, 6};

    int hi = values[n - 1];
    int lo = values[0];
    printf("What number? \n");
    scanf("%d", &value);

    if (!binarysearch(value, values, n, 0, 5))
        printf("Number not present in array\n");
}

您可以尝试此算法 online，使用 1 到 13 之间的随机整数，如果您遵循 link，则有 50% 的机会找到该数字。

从 C 中的递归二进制搜索返回布尔值

returning boolean from a recursive binary search in C

c

recursion

cs50