In this example (section 3.3) from The C Programming Language book by Dennis M. Ritchie and Brian W. Kerninghan, I think there is something wrong with this code, and indeed when I ran it, it indeed didn't work as expected.
Here is the original code from the book:
/* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */
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 */
}
So, this function here is supposed to search for an integer in an array of integers and then if it found it, the function will return its position, otherwise it will return -1. And the first obvious wrong thing in it is the test low <= high in the wile loop, which will always stay True in this function, and therefore this loop will run indefinitely and never end (and this is what happened when I ran it, it got stuck in an infinite loop apparently(edit: if x is not in v, otherwise it works correctly but a good program is supposed to cover all cases)), and the solution to this is to remove the "or equals" part of the test, meaning to change it to low < high. And the second mistake is with the first if statement, because when it finds that x < v[mid] it sets high to mid + 1 which is obviously wrong because if x value is less than the middle value (The v array is sorted) then x will be in the indexes less than the middle index and therefore the range that we should check would be 0 to mid -1 but that is not the case, because in the book they included mid and mid + 1 in the range which we know they are greater than x (because x < v[mid]), so they should have set high to mid - 1 instead.
So, my question is: Did they really make a mistake in this example, or did I misunderstand? And if they did, is what I said about the mistakes correct or not? And finally, here's an implementation of the function along with the corrections I stated above in this C code (that worked as intended when I executed it) below:
#include <stdio.h>
int binsearch(int x, int v[], int n);
int main() {
int n = 10, x = 25;
int v[10] = {0, 5, 10, 19, 20, 21, 22, 23, 25, 70};
int position = binsearch(x, v, n) + 1;
if (position) /*equivalent to (position != 0) since position will equal 0 when binsearch returns -1*/
printf("x is at: %d", position);
else
printf("x is not found.");
return 0;
}
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 */
}
And one last question, when x is indeed in v at the end when the corresponding index will be found it will be returned in the return mid; statement but then when we get out of the while loop, we find that -1 will also be returned, wouldn't that overwrite the returned value from the while loop?
The 1st edition of K&R appears to include the following code which is indeed bugged and can loop forever:
/* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */
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; /* bug here */
else if (x > v[mid])
low = mid + 1;
else /* found match */
return mid;
}
return -1; /* no match */
}
The 2nd edition of K&R includes the following, corrected version:
/* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */
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; /* correction here */
else if (x > v[mid])
low = mid + 1;
else /* found match */
return mid;
}
return -1; /* no match */
}