c - 数组中的二分查找

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

我挣扎了几个小时试图做到这一点。

任何帮助将不胜感激。在此先感谢您。

编辑:每个语句的循环中变量“低”和“高”的值应该是多少？

#

#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;

}