binary search algorithm

[johnmerlino]

In the below example, a binary search function decides if a particular value x occurs in the sorted array v. The elements of v must be in increasing order. The function returns the position (a number between 0 and n-1) if x occurs in v, and -1 if not:

int binsearch(int x, int v[], int n)
{
    int low, high, mid;
    low = 0;
    high = n - 1;

    while (low <= high) {
        mid = (low+high)/2;
        if (x < v[mid])
            high = mid + 1;
        else if (x > v[mid])
            low = mid + 1;
        else
          /* found match */
          return mid;
    }
    return -1;
    /* no match */
}

I understand how it works generally: when x is 3 and n is 10, we initialize low to 0 and high to 9. The while statmeent executes, as 0 is less than 9. We divide 9 by 2 and get 4. x is less than 4, so we set high to 5. 0 is still less than 5, so we divide 5 by 2 and get 2. x is greater than 2, so we set low to 3. 3 is less than 5, and since it's not less than the mid or greater than the mid, we return 3, which is the position of x in the sorted array v.

But one question: why do we need to add 1 to mid for this to work?
mid + 1

[LB]

Because you don't want to include the element that you just confirmed was not what you were looking for?

[johnmerlino]

But if x is less than the value stored in 4, why we set high to 5. It's obviously also going to be less than the value stored in 5.

[LB]

I think line 10 was supposed to use a minus sign...

[johnmerlino]

You know, in the book there is no minus sign. But I think you are right because with that plus sign there, it seems to create an infinite loop.

[johnmerlino]

Yeah it has to be a minus sign. With a minus sign the algorithm makes sense. Without it, it creates an infinite loop.

[LB]

Which book is this example from?

[johnmerlino]

This was actually a book on C and it was a minus not a plus. It was scratched out or something.