Binary search in an array

Question

Can someone correct and complete the code below? i'm unable to do that...

I want first a random number generated from an array with the values 1 to 20.

The program has to find what is the random number by guessing at different stages the middle number of the array and eliminate half of the remaining numbers after every loop.

Let’s say the random number is 13

As the array is between 1 and 20 , the first guess number is 10 as this is the number in the middle of the array.

As the guess number 10 is lower than the random number 13, the next test is then 15 ( which corresponds to ( 20 +10 ) /2).

As the guess number 15 is higher than the random number 13, the next test is then 12 ( which corresponds to ( 15 +10 ) /2).

As the guess number 12 is lower than the random number 13, the next test is then 13 ( which corresponds to ( 12+15 ) /2).

The guess number now match the random number

There is my code

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

}

and there is the output expected

Output expected ( for 13 as the random number):

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

I struggled for hours trying to do that.

Any help would be highly appreciated.Thank you in advance.

EDITED : What should be the value of the variables "low" and "high" in the loop for each statement ?

#

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

}

What's your question? Are you looking for feedback on your code? Does it not work and you need debugging help? — Stephen Newell
– Stephen Newell, Commented May 21, 2020 at 14:57
You need to recalculate middle within the loop, and update low and high according to whether you're going left or right. — 500 - Internal Server Error
– 500 - Internal Server Error, Commented May 21, 2020 at 15:12
You may need to worry about high = 20; vs high = 19; similarly. In the loop, calculate middle = (low + high) / 2;, and when you make a directional choice, adjust low or high. — Jonathan Leffler
– Jonathan Leffler, Commented May 21, 2020 at 15:19
@qwerty1805 The while is a loop, but the condition is wrong and also the value of the condition never changes inside the loop body, so the loop is either infinite or never executed. — Arkku
– Arkku, Commented May 21, 2020 at 15:33
You will want to add a break somewhere in the loop, otherwise it's an infinite loop. — David R Tribble
– David R Tribble, Commented May 21, 2020 at 15:36

Hitokiri · Accepted Answer · 2020-05-21 16:01:02Z

You should compare the value of array (array[middle]) with randomValue, because if the array is not from 1 to 20 as you did (for example, int array [20] = {0, 3, 4, 10, 15, ...}), your program will be never correct.

The code for while loop (the explication in the comment of code):

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.
        }

    }

The output when 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

The complete code:

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

}

Craig Estey · Accepted Answer · 2020-05-21 15:54:57Z

You're starting high at 20. But, it's an index so you want 19.

Your while loop condition is wrong. middle can be greater than randomValue in search. You really want to compare low and high instead.

You need two variables: one for current index and one for current value, not just a single middle value. The "value" variable should be the value that is fetched from the array index.

You have to change the middle index value according to the tests in the loop.

You have to stop your loop with break when you get a match.

Here's a version of your code with the bugs annotated and fixed:

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

Here's a cleaned up version:

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

Collectives™ on Stack Overflow

Binary search in an array

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related