0

The program 'randomly' chooses a set of 8 numbers and then the user has to guess as many of those numbers as they can. But even if I type in the numbers in this array of random numbers, the binary_search function doesn't find that exact number in the array of 'random' numbers. I can't seem to find the mistake in my binary_search function (at least I suspect that that's where the problem is). I have tried the program with large SIZE of numbers and small too. Could anyone help me please?

#define SIZE 3
#define min  1
#define max  36

int random();
bool binary_search(int value, int values[], int n);

int main(void)
{
    int numbers[SIZE];
    for(int i = 0; i < SIZE; i++)
        numbers[i] = random();
    int score = 0;
    int n[SIZE];
    int number_user;


    for(int i = 0; i < SIZE; i++)
    {   
        //Type in a number
        do
        {
            printf("Search number no.%d:\n> ", i + 1);
            n[i] = GetInt();

            //Wrong input number
            if(n[i] < min || n[i] > max)
            {
                printf("\nNumber should be between %d - %d!!!\n\n", min , max);
            }
        }
        while(n[i] < min || n[i] > max);

        //THE PROBLEMATIC STUFF - START
        number_user = n[i];
        if (binary_search(number_user, numbers, SIZE))
        {
            printf("FOUND!!!\n");
            score += 1;
        }
        else 
        {
            printf("NOT IN THE LIST\n");
        }
        //PROBLEMATIC STUFF - FINISH
    }

    //scoring
    printf("\n\n*******SCORE*******\n");
        //print your numbers
        for(int i = 0; i < SIZE; i++)
        {
            printf(" %d", n[i]);
            if(i != SIZE - 1)
                printf(",");
            if(i == SIZE - 1)
                printf(".\n");
        }

        //print right numbers
        printf("\nRight numbers are:");
        for(int i = 0; i < SIZE; i++)
        {
            printf(" %d", numbers[i]);
            if(i != SIZE - 1)
                printf(",");
            if(i == SIZE - 1)
                printf(".\n");
        }

    int result = score / SIZE * 100;
    printf("Your score is: %d / %d , %d %%\n", score, SIZE, result);


    return 0;    
}
 //PROBLEM START
bool binary_search(int value, int values[], int n)
{
    int beginning = 0;
    int ending = n - 1;

    int middle;

    while (ending >= beginning) 
    {    
        middle = (beginning + ending) / 2; 
        for(int i = 0; i < SIZE; i++)
        {
            //look at middle of list if (binary_search(n, numbers, SIZE))
            if(values[middle] == value)
                //if number found, return true 
                return true;

            //else if middle higher, search left 
            else if(values[middle] > value)
                ending = middle - 1;

            //else if middle lower, search right 
            else if(values[middle] < value)
                beginning = middle + 1;
        } 
    }
    return false; 
}
//PROBLEM FINISH

int random()
{
    int r = rand() % ((max - min + 1) + min);

    return r;
}
3
  • What's the point of the for loop in your binary search? Commented Nov 26, 2013 at 22:38
  • I think it is necessary to sort up to before to search for numbers. Commented Nov 26, 2013 at 22:41
  • No, it really isn't... Commented Nov 26, 2013 at 22:41

3 Answers 3

5

Binary search is about sorted array / list / etc ... and your program feels randomal numbers.

See https://en.wikipedia.org/wiki/Binary_search_algorithm (the second line).

Sign up to request clarification or add additional context in comments.

Comments

2

Inside your binary search function you have this loop...

for(int i = 0; i < SIZE; i++)
{
    ...
} 

Inside it, you change the beginning and ending values many times without changing middle. This means beginning and ending are adjusted several times based on a single value of middle, which in turn means it can "disqualify" ranges of the array that would actually have the number you're searching for.

Furthermore, as MeNa points out in his/her answer, binary search is meant for searching ordered data sets. It's useless for arrays in random order.

Comments

1

If that isn't homework you can try using bsearch if you have it. (It's a POSIX function.)

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.