c - 二分查找 - 如果我从列表中间添加或减去 "1"，我会得到中间数字左边的第一个数字还是一个数值？

Question

我的疑问发生在 while 循环内部。当我将“1”添加到列表的最小值和最大值时，我在做什么 - 我是向列表中的数字的左侧/右侧移动还是以数字方式更改值？谢谢!

bool search(int value, int values[], int n) {
    if (n < 0) {
        return false;
    }

    // beginning and final portions
    int min = 0;
    int max = n - 1;

    // middle variable
    int mid = n / 2;

    // this massive number will be useful to guarantee that the search function 
    // can handle incredibly large arrays
    const int MAX = 65536;

    while (n > 0) {
        if (value > value[middle]) {
            min = middle + 1;
        } else
        if (value < value[middle]) {
            max = middle - 1;
        } else
        if (value == value[middle]) {
            return true;
        }
    }
}

Answer 1

你的功能在很多方面都被破坏了:

• 它没有实现二分搜索
• MAX 并不大规模，甚至没有在任何地方使用
• middle 未定义，并且在循环中不会被修改。
• value > value[middle] 可能应该是 value>values[mid]...

这是一个简单的正确实现(借自 Matt Timmermans):

bool search(int value, int values[], size_t n) {
    size_t pos = 0;
    size_t limit = n;

    while (pos < limit) {
        size_t middle = pos + ((limit - pos) >> 1);

        if (values[middle] < value)
            pos = middle + 1;
        else
            limit = middle;
    }
    return pos < n && values[pos] == value;
}