-2

我使用重复进行了这个二进制搜索，但是，当我得到答案（布尔值）时，我似乎在重复的过程中跌跌撞撞，无法从函数中得到正确的答案。有人可以帮忙吗？请评论代码。

// binary search
bool 
search(int value, int array[], int n)
{

    // the array has more than 1 item
    if (n > 1)
    {
        int m = (n/2);

        // compares the middle point to the value
        if (value == array [m])
            return true;

        // if the value given is lower than the middle point of the array
        if (value < array [m])
        {
            int *new_array = malloc (m * sizeof(int));

            // creating a new array with the lower half of the original one
            memcpy(new_array, array, m * sizeof(int));

            // recalling the function
            search (value, new_array, m);
        }


        // if the value given is greater than the middle point of the array
        else
        {
            int *new_array = malloc (m * sizeof(int));

            // creating a new array with the upper half of the original one
            memcpy(new_array, array + (m + 1), (m  * sizeof(int)));

            // recalling the function
            search (value, new_array, m);
        }
    }

    else if (n==1)
    {

        // comparing the one item array with the value
        if (array[0] == value)
            return true;

        else
            return false;

    }

    if (true)
        return true;

    else 
        return false;



}
4

3 回答 3

0

正如 amint 所提到的，复制数组完全违背了进行二进制搜索的目的。其次，我相信您的意思是递归，而不是重复。

需要考虑的事情：与其复制数组，不如考虑如何通过将一组索引传递给数组（如开头和结尾）来获得相同的结果。

至于您的实际问题，如何通过递归返回布尔值。从递归函数返回值的问题是每次迭代都必须传递值。你可以把它想象成一个责任链委托。第一个电话就像公司的负责人。他没有做所有的工作，所以他把它委托给他的助手，但他先做一件工作。然后助手有助手等。一路乌龟；）

但是，为了取回价值，链中的每个人都必须将其还给他们之前的人。回到编程，这意味着每次递归调用搜索时，都需要返回该值。

最后，一旦你有了这些东西，你就需要更好地定义你的基本案例。我假设这就是你想要做的事情 if (true) return true; 否则返回假；但是，正如 H2CO3 所指出的，这没有多大意义。事实上，你之前的 if 语句if (n == 1) ...应该确保之后的代码永远不会被执行。

于 2012-11-08T19:02:07.983 回答
0

您应该return search(...);，而不仅仅是调用该search()方法 - 否则返回值不会冒泡。

此外，请注意，此算法是O(n)（与数组大小成线性关系）并且会泄漏内存并且效率非常低，因为您在每次迭代中复制了一半的数组。
实际上，它可能使算法比简单的线性搜索元素慢得多。

一个好的二分搜索不需要复制数组的一半——它只是“看”它的一半。可以通过array+m作为数组发送（对于上半部分）来实现，对于下半部分，只有递减n就足够了。

于 2012-11-08T18:52:12.057 回答
0

您需要返回递归搜索的值。

return search (value, new_array, m);

否则，当您调用搜索时，您只是丢掉了答案

于 2012-11-08T18:51:55.270 回答