c - 无限递归 : binary search & asserts

标签 c recursion binary-search

我正在用 C 语言编写一个二分查找的实现,并且无缘无故(对我而言)得到了无限递归。这是我的代码:

/*Orchestrate program*/
int main(int argc, char* argv){
    int array[] = {1,2,3,3,3,6,7,8,9,9,20,21,22};
    int length = 13;
    int key = 23;
    binary_search(key, array, 0, length - 1);
    return 0;
}

int binary_search(int key, int array[], int first_index, int last_index){
    int middle;
    middle = (first_index + last_index)/2;
    if (first_index == last_index){
        if (array[middle] == key){
            printf("%d has been found at position %d\n", key, middle+1);
        }
        printf("item not found");
    }
    else if (key > array[middle]){
        binary_search(key, array, middle, last_index);
    }
    else if (key < array[middle]){
        binary_search(key, array, first_index, middle);
    }
}

根据我在 main 中的键的值,我猜问题出在第一个 else if 上,但我不确定为什么。如果我要删除 first_index == last_index 行,该算法可以正常工作,但仅当该项目位于数组中时。如果该项目不在数组中,我自然会得到无限递归。

此外,我试图通过删除 first_index == last_index 行并在函数末尾放置一个 return -1; 来解决这个问题,但我得到了我现在遇到同样的问题。

编辑:

综合我从几个不同用户那里收到的建议,我得出了以下解决方案(已修复一个错误和未嵌套的决策):

void binary_search(int key, int array[], int first_index, int last_index){
    int middle;
    middle = (first_index + last_index)/2;

    if (array[middle] == key){
        printf("%d has been found at position %d\n", key, middle+1);
    }
    if (first_index == last_index){
        printf("item not found");
    }
    else if (key > array[middle]){
        binary_search(key, array, middle + 1, last_index);
    }
    else if (key < array[middle]){
        binary_search(key, array, first_index, middle - 1);
    }
}

我有一个后续问题:有没有一种方法可以使用断言来帮助我自己找到这个解决方案? (我只是在学习断言,所以我想知道在哪里可以应用它们)

最佳答案

您搜索排序数组的更小范围。您的数组的边界是包容性的。

递归的基本情况是:如果范围为空,则找不到键。或者,在代码中:

if (first_index > last_index){
    printf("Not found\n");
}

只有在确定范围不为空后,才应计算和比较范围的中间元素。在这种情况下,您会得到三种结果:

  • 中间元素是关键:宾果游戏!
  • 中间元素小于key:搜索数组的右半部分,排除中间元素,我们已经检查过了。
  • 中间元素比键大:同上,但左半部分。

把这些放在一起:

void binary_search(int key, int array[], int first_index, int last_index)
{
    if (first_index > last_index){
        printf("Not found\n");
    } else {
        int middle = (first_index + last_index) / 2;

        if (array[middle] == key) printf("%d at index %d\n", key, middle);

        if (key > array[middle]){
            binary_search(key, array, middle + 1, last_index);
        } else {
            binary_search(key, array, first_index, middle - 1);
        }
    }
}

这个函数还有两点困扰着我:

  • 打印索引的函数没有什么实际用处。打印应该由客户端代码完成,即由调用函数的代码完成。返回找到的索引或“未找到”的特殊值。
  • 范围包含边界。这不是很像 C。在 C 语言中,范围通常由包含的下限和不包含的上限来描述。这就是数组索引和 for 循环的工作原理。遵循此约定意味着您的客户端代码不必执行笨拙的 length - 1 计算。

所以这是一个变体,如果键不在数组中,则返回索引或 -1:

int binary_search1(int key, int array[], int first_index, int last_index)
{
    if (first_index < last_index){
        int middle = (first_index + last_index) / 2;

        if (array[middle] == key) return middle;

        if (key > array[middle]){
            return binary_search1(key, array, middle + 1, last_index);
        } else {
            return binary_search1(key, array, first_index, middle);
        }
    }

    return -1;
}

并测试它:

int main()
{
    int arr[6] = {3, 4, 6, 8, 12, 13};
    int i;

    for (i = 0; i < 20; i++) {
        int ix = binary_search(i, arr, 0, 6);

        if (ix < 0) {
            printf("%d not found.\n", i);
        } else {
            printf("%d at index %d.\n", i, ix);
        }
    }

    return 0;
}

请注意,您的原始数组有重复的条目。这没关系,但您将获得任何重复值的索引,不一定是第一个。

关于c - 无限递归 : binary search & asserts,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29771550/

相关文章:

检查数组是否包含所有元素

c - 机器人如何固定距离跟踪球?

javascript - 我是否正确使用了递归?

c++ - 快速搜索以查找事件范围

java - 我不可能理解所描述的字符串搜索方法。什么是 uFFFF?

c - 使用 OpenCV 查找物体的高度

c - 未定义表达式的汇编程序调试

c++ - 杆切割 - 递归

javascript - 如何递归调用ajax直到某个条件成立?

c - 在 C 中,是否保证 1/2 == 0?