CODEWITHSUNDEEP
cbinary-search
Jorgel
Jorgel

Reputation: 930

What's wrong with this Binary Search function?

I am tring to solve a Spoj problems of Binary Search but I keep getting "wrong answer" and I can't see my problem. Here is my bsearch function:

int binarySearch(int numbers[], int size, int key)
{
    int start = 0;
    int end = size - 1;
    int middle;

    while(start <= end)
    {
        middle = start + (end - start)/2;

        if(key < numbers[middle])
            end = middle - 1;
        else if(key > numbers[middle])
            start = middle + 1;
        else
            return middle;
    }

    return -1;
}

And this is my main function

int main()
{
    int *numbers;
    int n_numbers, n_queries, key, i, found;

    scanf("%d %d", &n_numbers, &n_queries);
    numbers = (int*)malloc(n_numbers * sizeof(int));

    for(i = 0; i<n_numbers; i++)
        scanf("%d", &numbers[i]);

    for(i = 0; i<n_queries; i++)
    {
        scanf("%d", &key);
        found = binarySearch(numbers, n_numbers, key);
        printf("%d\n", found);
    }

    return 0;
}

Here is the SPOJ problem: http://www.spoj.com/problems/BSEARCH1/

Upvotes: 0

Views: 601

Answers (3)

Omri Barel
Omri Barel

Reputation: 9490

The problem is that you are required to return the location of the first occurrence (starting from zero), and you are returning as soon as you find the key.

But it's possible that the array is: 0 1 1 1 1 1 1 1 1 1 1 1 2

And the key is 1. You should return 1 (the location of the first occurence) and instead you are returning 6.

Upvotes: 3

Mike
Mike

Reputation: 491

Not totally clear which C based language you are using but might the expression (end - start)/2 possibly return a floating point value that is then truncated to an integer when you actually would want the value rounded?

Upvotes: 0

Woot4Moo
Woot4Moo

Reputation: 24336

Your algorithm is correct. The data is not sorted, so you binary search algorithm cannot correctly zero in on the solution.

Upvotes: 1

Related Questions