c - 无限递归 : binary search & asserts

Question

我正在用 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);
    }
}

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

Answer 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;
}

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