数组中的二分查找

Question

有人可以更正并完成下面的代码吗？我做不到...

我首先想要一个从值 1 到 20 的数组生成的随机数。

程序要通过在不同阶段猜测数组的中间数字来找到随机数，并在每次循环后消除剩余数字的一半。

假设随机数是13

由于数组介于 1 和 20 之间，第一个猜测数字是 10，因为这是数组中间的数字。

由于猜测数字10小于随机数13，所以下一次测试是15（对应（20+10）/2）。

由于猜测数字15大于随机数13，所以接下来的测试是12（对应（15+10）/2）。

由于猜测数字12小于随机数13，所以下一次测试是13（对应（12+15）/2）。

现在猜测的数字与随机数匹配

有我的代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {

    srand(time(NULL));
    int array [20] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14,15,16,17,18,19,20};
    int randomIndex = rand() % 20;
    int randomValue = array[randomIndex];
    int low = 0;
    int high = 20;
    int middle = (low + high) / 2;


    printf("The random number to find is %d\n", randomValue);

    while (middle <= randomValue) {

        if (middle < randomValue) {
            printf("The number %d is lower than the random number\n", middle);

        }

        if (middle > randomValue) {
            printf("The number %d is lower than the random number\n", middle);
        }

        if (middle == randomValue) {
            printf("The number %d  is the correct random number", middle);
        }

    }
    return 0;

}

并且有预期的输出

预期输出（13 作为随机数）：

The number 10 is lower than the random number

The number 15 is higher than the random number

The number 12 is lower than the random number

The number 13 is the correct random number

我为此努力了好几个小时。

任何帮助都将是高度appreciated.Thank你提前。

已编辑：每个语句的循环中变量 "low" 和 "high" 的值应该是多少？

#

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {

    srand(time(NULL));
    int array [20] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14,15,16,17,18,19,20};
    int randomIndex = rand() % 19;
    int randomValue = array[randomIndex];
    int low = 0;
    int high = 19;
    int middle = (low + high) / 2;


    printf("The random number to fine is %d\n", randomValue);

    while (middle <= randomValue) {

        if (middle < randomValue) {
            printf("The number %d is lower than the random number\n", middle);
            low  = ;
            high = ;
            middle = (low + high) / 2;
        }

        if (middle > randomValue) {
            printf("The number %d is lower than the random number\n", middle);
            low  = ;
            high = ;
            middle = (low + high) / 2;

        }

        if (middle == randomValue) {
            printf("The number %d  is the correct random number", middle);
        }

    }
    return 0;

}

Answer 1

您应该将数组 (array[middle]) 的值与 randomValue 进行比较，因为如果数组不是像您那样从 1 到 20（例如,int array [20] = {0, 3, 4, 10, 15, ...}), 你的程序永远不会正确。

while loop的代码（代码注释中的说明）：

while (high >= low) {
        int middle = (low + high) / 2; // update middle in each iteration of while loop

        if (array[middle] < randomValue) {
            printf("The number %d is lower than the random number\n",array[middle]);
            low = middle+1; // If randomValue greater than value at middle position, we can ignore left half 

        }

        if (array[middle] > randomValue) {
            printf("The number %d is lower than the random number\n", array[middle]);
            high = middle - 1; // If randomValue smaller than value at middle position, we can ignore right half
        }

        if (array[middle] == randomValue) {
            printf("The number %d  is the correct random number", array[middle]);
            break; // exit while loop if you find out the number.
        }

    }

randomValue = 13时的输出：

The random number to find is 13                                                                                                                             
The number 10 is lower than the random number                                                                                                               
The number 15 is lower than the random number                                                                                                               
The number 12 is lower than the random number                                                                                                               
The number 13  is the correct random number

完整代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {

    srand(time(NULL));
    int array [20] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14,15,16,17,18,19,20};
    int randomIndex = rand() % 20;
    int randomValue = array[randomIndex];
    int low = 0;
    int high = 19;


    printf("The random number to find is %d\n", randomValue);

    while (high >= low) {
        int middle = (low + high) / 2;

        if (array[middle] < randomValue) {
            printf("The number %d is lower than the random number\n",array[middle]);
            low = middle+1;

        }

        if (array[middle] > randomValue) {
            printf("The number %d is lower than the random number\n", array[middle]);
            high = middle - 1;
        }

        if (array[middle] == randomValue) {
            printf("The number %d  is the correct random number", array[middle]);
            break;
        }

    }
    return 0;

}

Answer 2

你从 20 开始 high。但是，它是一个 index，所以你想要 19。

你的 while 循环条件是错误的。 middle 在搜索中可以大于randomValue。您真的想比较 low 和 high。

您需要两个变量：一个用于当前索引，一个用于当前值，而不仅仅是单个 middle 值。 "value" 变量应该是从数组索引中获取的值。

你必须根据循环中的测试更改中间索引值。

当你得到匹配时，你必须用 break 停止你的循环。

这是您的代码版本，其中包含已注释和修复的错误：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int
main()
{

    srand(time(NULL));
    int array[20] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
        11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
    int randomIndex = rand() % 20;
    int randomValue = array[randomIndex];
    int low = 0;
// NOTE/BUG: high is an _index_ so it must be one less
#if 0
    int high = 20;
#else
    int high = 19;
#endif
// NOTE/BUG: this must be done inside the loop
#if 0
    int middle = (low + high) / 2;
#else
    int middle;
    int middle_index;
#endif

    printf("The random number to find is %d\n", randomValue);

// NOTE/BUG: wrong loop condition -- middle can be higher during search
// NOTE/BUG: in the general case we need a two variables: one for current
// index and one for current value
#if 0
    while (middle <= randomValue) {
#else
    while (low <= high) {
#endif
        middle_index = (low + high) / 2;
        middle = array[middle_index];

// NOTE/BUG: none of these change low/high
        if (middle < randomValue) {
            printf("The number %d is lower than the random number\n", middle);
#if 1
            low = middle_index + 1;
#endif
        }

        if (middle > randomValue) {
            printf("The number %d is lower than the random number\n", middle);
#if 1
            high = middle_index - 1;
#endif
        }

        if (middle == randomValue) {
            printf("The number %d  is the correct random number\n", middle);
#if 1
            break;
#endif
        }
    }

    return 0;
}

这是清理后的版本：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int
main()
{

    srand(time(NULL));
    int array[20] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
        11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
    int randomIndex = rand() % 20;
    int randomValue = array[randomIndex];
    int low = 0;
    int high = 19;
    int middle;
    int middle_index;

    printf("The random number to find is %d\n", randomValue);

    while (low <= high) {
        middle_index = (low + high) / 2;
        middle = array[middle_index];

        if (middle < randomValue) {
            printf("The number %d is lower than the random number\n", middle);
            low = middle_index + 1;
        }

        if (middle > randomValue) {
            printf("The number %d is lower than the random number\n", middle);
            high = middle_index - 1;
        }

        if (middle == randomValue) {
            printf("The number %d  is the correct random number\n", middle);
            break;
        }
    }

    return 0;
}

数组中的二分查找

Binary search in an array

c

arrays

binary-search