CODEWITHSUNDEEP
c++algorithmbinary-search
mau5padd
mau5padd

Reputation: 405

Binary search not returning correct value

I'm implementing the binary search algorithm in C++, but the algorithm isn't returning the correct value. The code can be found here.

template<class T>
int binary_search(T search_value, T search_array[]) {

    int mid; /* The middle element of the remaining array to be searched. */
    int min = 0; /* The first index of the array. */
    /* This forumla gives us the size of the array. */
    int max = sizeof(search_array)/sizeof(search_array[0]);

    /* Continue searching until min >= max. */
    while (min < max) {
        /* Compute the value of mid using a formula that won't produce a number
         * larger than the maximum allowed value of an integer. */
        mid = (max-min)/2 + min;

        /* Depending the whether search_value is larger or smaller than the
         * value of whatever is at search_array[mid], set one of mid and max
         * equal to mid. */
        if (search_value > search_array[mid])
            min = mid + 1;
        else if (search_value < search_array[mid])
            max = mid + 1;
        else {
            return mid;
        }
    }

    return -1;
}

Given an array {0, 1, 3, 5, 7, 9} and searching for 3, the function should return 2, the index of 3 in the array. My function is returning -1 though, which means 3 was not found in the array. Where's the problem?

Upvotes: 0

Views: 468

Answers (7)

e7mac
e7mac

Reputation: 553

Your max needs to be one less as the index starts from 0.

Upvotes: 1

Jim Fell
Jim Fell

Reputation: 14264

This line is concerning:

int max = sizeof(search_array)/sizeof(search_array[0]);

sizeof(search_array) is going to be the size of a pointer, 4 or 8 bytes depending on the platform. Typically, I try to avoid the use of sizeof on variables. It plays nicer used on types. For example, in your case sizeof(T).

Upvotes: 2

ouah
ouah

Reputation: 145899

int max = sizeof(search_array)/sizeof(search_array[0]);

search_array is a pointer not an array.

A parameter of type array of T in a function prototype is automatically adjusted to a pointer to T.

Upvotes: 2

orlp
orlp

Reputation: 117791

This line does not do what you think it does:

int max = sizeof(search_array)/sizeof(search_array[0]);

Because arrays automatically decay to pointers when passed into a function this will effectively be equal to this:

int max = sizeof(void*)/sizeof(search_array[0]);

Which is not what you wanted. Either use std::vector which stores the size for you or a manual size_t array_length argument.

Upvotes: 2

user405725
user405725

Reputation:

This line is a at least one problem:

int max = sizeof(search_array)/sizeof(search_array[0]);

Arrays are not passed through the function, so your declaration:

int binary_search(T search_value, T search_array[])

... is the same as:

int binary_search(T search_value, T *search_array)

And thus max is size of the pointer divided by the size of element, so in the best case scenario it could be up to 6, but most likely is 0 or 1.

I think in C++ you can pass array by reference and know its size using form of declaration like this:

template <size_t array_length>
void foo (const char (&data) [array_length])
{
   // ...
}

Upvotes: 3

Greg Hewgill
Greg Hewgill

Reputation: 994471

There's a bug in your implementation:

else if (search_value < search_array[mid])
    max = mid + 1;

should be:

    max = mid - 1;

Upvotes: 2

Manlio
Manlio

Reputation: 10864

int max = sizeof(search_array)/sizeof(search_array[0]);

This approach is not good to compute the size of the array, it works only in the function where you create your array.

Pass the size of your array as a parameter of your function, it's the easiest approach.

Upvotes: 5

Related Questions