Binary search in Kernighan and Ritchie's C book-CodePudding

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?

CodePudding user response：

Definitely an OP typo.

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

K&R book looks OK.

CodePudding user response：

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.

CodePudding user response：

the compiling DOES end . the execution DOES NOT end.

You have initially

LOW MIN HIGH
0   1   2

So, initially, you have x<v[mid=2]. So it enters if (x < v[mid]). This will set high = mid 1 = 2 and does nothing more.

So the next loop you will be in the same state

LOW MIN HIGH
0   1   2

If you set

 if (x < v[mid])
   high = mid;
 else if (x > v[mid])
   low = mid;
 else /* found match */
   return mid;

this will work.

CodePudding user response：

Here's what happens when the above code executes

int binsearch(int x, int v[], int n){ // x = 3, v = {3,4,7}, n = 3
   int low, high, mid;
   low = 0;
   high = n - 1;                      // high = 2
   while (low <= high) {              // 0 <= 2 ... true
     mid = (low high)/2;              // mid = (0 2)/2 = 2/2 = 1
     if (x < v[mid])                  // 3 < v[1] ... 3 < 4 ... true
       high = mid   1;                // high = 1   1 = 2
     else if (x > v[mid])
       low = mid   1;
     else /* found match */
       return mid;
   }
   return -1; /* no match */
 }

As you can see, iteration does not end. The value of high doesn't change, and no expression that was executed tried to alter the values of mid and low.

It's possible that the Kernighan and Ritchie text contained an error, but more likely it wasn't copied correctly. The fact that mid 1 appears two lines further down suggests the latter.

It looks like the line high = mid 1; should read simply high = mid;. Certainly that gives the correct result in your test case. As an exercise, you should try with larger lists, containing odd and even numbers of elements, and see how the code does. Does it behave differently if the number we're looking for is in the upper half of the array?