Binary search in Kernighan and Ritchie's C book

Question

Kernighan and Ritchie gives us a function to do binary research over an array. Their function is the following:

#include <stdio.h>


/* 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 */
 }


int main() {
  int a[3]={3,4,7};
  int z = binsearch(3,a,3);
  printf("%d\n", z);
}

But once I execute the code there is no result whatsoever and the compiling does not end. Is there anything wrong with the array I chose to use for trying the code?

Try single-stepping with a debugger. On entry to the loop we have `low = 0`, `mid = 1`, `high = 2`. So `x < v[mid]` is true, and we do `high = mid + 1;`. This sets `high = 2`, but `high` was already 2 so nothing has changed and the next iteration does exactly the same thing. — Nate Eldredge, Oct 13 '21 at 14:48
@nate: did you actually look at K&R? At least in the copy I have, the line correctly reads `high = mid - 1` (top of page 58). — rici, Oct 13 '21 at 15:16
@SteveSummit This question and some of the comments and answers are a clear illustration of why even experienced programmers should use already-debugged library functions instead of "I can just roll my own in a few minutes." — rici, Oct 13 '21 at 16:37
It's famously been observed that the binary search algorithm was first described in 1946, but that it was not published as an implementation without bugs until 1962. But K&R (the people) knew this, and K&R (the book) was published after 1962, and Kernighan is [fanatical about testing](https://www.cs.princeton.edu/~bwk/testing.html), so it's inconceivable to me that a binary search routine in K&R could be incorrect. — Steve Summit, Oct 13 '21 at 16:46
@rici I can argue that one either way. On the one hand, I agree, an experienced programmer should be extremely wary of reimplementing binary search, and should prefer a prewritten one if at all possible, because of the [notorious difficulty of implementing it correctly](https://stackoverflow.com/questions/504335). But on the other hand, I don't see how you can call yourself a professional programmer if you *can't* implement binary search correctly, and demonstrate (with a proper unit test suite) that you have done so. — Steve Summit, Oct 13 '21 at 16:48
@Steve: I didn't intend to imply that anyone couldn't write and test binary search; just that the temptation to do a quick-and-dirty should be resisted. I think we agree about how easy it is to get wrong. — rici, Oct 13 '21 at 17:11
Notes: Obscure UB/failure in this code include `low+high` overflow, array element count > `INT_MAX`, `n == INT_MIN`. Changing `int v[]` to `double` does not handle NANs correctly. Better to use `const int v[]`. IMHO, code benefits from many sets of eyes. — chux - Reinstate Monica, Oct 13 '21 at 17:33
@rici: Hmm. I only have a paper copy of the first edition, and it has the correct code `high = mid - 1;`. For the second edition, all I could find was [this bootleg copy](https://raw.githubusercontent.com/auspbro/ebook-c/master/The.C.Programming.Language.2Nd.Ed%20Prentice.Hall.Brian.W.Kernighan.and.Dennis.M.Ritchie..pdf) which does have the bug on page 54 - but it could have been an error in a particular printing, or even an OCR failure. But perhaps that's the edition that OP is using. — Nate Eldredge, Oct 13 '21 at 17:34
@rici I think every time I've written it (which is plenty of times!), my first try has turned into an infinite loop, which doesn't even seem to be listed among the common pitfalls at [this question](https://stackoverflow.com/questions/504335) :-\ — Steve Summit, Oct 13 '21 at 17:35
@NateEldredge: Perhaps. I have a copy of the second edition, and it doesn't look a lot like that bootleg, which is missing the index and colophon and looks like it has been paginated from the PDF rather than the book (where the cover is not page 1 :-). So it's probably a pirated version, as well as being a bootleg. It certainly is possible that OP is using it. If that's the case, they should find a better one. — rici, Oct 13 '21 at 18:17
http://cslabcms.nju.edu.cn/problem_solving/images/c/cc/The_C_Programming_Language_%282nd_Edition_Ritchie_Kernighan%29.pdf — KcFnMi, Dec 27 '22 at 12:55

score 2 · Answer 1 · answered Oct 13 '21 at 15:13

2

Definitely an OP typo.

// if (x < v[mid]) high = mid + 1;
if (x < v[mid]) high = mid - 1;  //  `+` --> `-`.

K&R book looks OK.

answered Oct 13 '21 at 15:13

chux - Reinstate Monica

143,097
13
135
256

This makes sense. There's no point in looking at the `mid` value again - if it matched what we were looking for, there'd be no need for another iteration. – Tim Randall Oct 13 '21 at 17:03
2

@Tim... to say nothing of an infinite number of iterations. Because if you don't change `high`, `low <= high` will continue to be true. – rici Oct 13 '21 at 17:06

score 0 · Answer 2 · answered Oct 13 '21 at 14:53

0

You can do some tracing, simply by doing printf at various places.

As a first you can print values of low, high and mid immediately after this line:

mid = (low+high)/2;

You will realise these 3 values never changes, because starting with low=0 and high=2, mid becomes 1. x is smaller than v[1] so you set high to mid+1 which is still 2 unchanged.

You can now correct your bug.

answered Oct 13 '21 at 14:53

One.Punch.Leon

602
3
10

If you're going to add `printf` statements, you also need to add curly braces otherwise the `if...else` construct gets messed up – Tim Randall Oct 13 '21 at 15:00

Binary search in Kernighan and Ritchie's C book

2 Answers2