### binary search algorithm

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:

 ``12345678910111213141516171819`` ``````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`
Because you don't want to include the element that you just confirmed was not what you were looking for?
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.
I think line 10 was supposed to use a minus sign...
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.
Yeah it has to be a minus sign. With a minus sign the algorithm makes sense. Without it, it creates an infinite loop.
Which book is this example from?
This was actually a book on C and it was a minus not a plus. It was scratched out or something.
Topic archived. No new replies allowed.