YoTengoUnLCD
YoTengoUnLCD

Reputation: 598

Very similar implementations of binarySearch with different parameters works equally fine. Why?

I was trying to make my own binary search function for a university project and came up with this:

int bSearch(int data[], int dim, int num)
{
    if(dim == 0)
        return 0;
    if(num == data[(dim-1)/2])
        return 1;
    if(num < data[(dim-1)/2])
        return bSearch(data,(dim-1)/2 - 1, num);
    if(num > data[(dim-1)/2])
        return bSearch(data + ((dim-1)/2) + 1, dim - (dim-1)/2 - 1 , num);
}

One of my friends came up with almost the same function but wherever I put (dim-1)/2 he wrote dim/2, and it looks like both are working equally fine, I came up with the (dim-1)/2 while trying a few examples and seemed to work.

Why does this difference (not) matter?

Upvotes: 0

Views: 43

Answers (1)

Fabio
Fabio

Reputation: 3067

The only difference is that how it divides the table in two to see in which section it is.

Traditionally you'd divide it in half, but you could divide it 10% and 90% and see in which section it is and it would also work, just wouldn't be optimal.

In your example, if you have a list with 10 numbers, it'd check the 4th to see if it's the number, then if it's not it'd see if it's smaller than the 4th and if it's not, it'd check to see if it's bigger. Your friends would do the same but with the 5th as the reference point. Both would work, but his is probably gonna be slightly faster for big tables.

Upvotes: 1

Related Questions