the arithmetic from k&r seems wrong

[Tak]

HI,EVERYONE:
That's my puzzle:
page52 of <The c programming language>(k&r),It writes:
/* 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 */
}

I tested the code in my program:
#include <stdio.h>

int bserch(int x, int st[], int n);

int main()
{
int array[6] = {1,2,3,4,5,6};
int findx;

scanf("%d",&findx);

printf("%d\n",bserch(findx,array,6));

return 0;
}

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

while (low <= high){
mid = (low+high)/2;
if (x < st[mid])
high = mid + 1;
else if (x > st[mid])
low = mid + 1;
else
return mid + 1;
}

return -1;
}

I can't receive the correct answer when I input 1 or 4.But when I
replace the statement "high = mid + 1; " by "high = mid;" the
program run correctly. What's wrong? Do I misunderstand? Or......?

Thanks for your HELP!

 

[Thad Smith]

HI,EVERYONE:
That's my puzzle:
page52 of <The c programming language>(k&r),It writes:
/* 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 */
}

I tested the code in my program:
#include <stdio.h>

int bserch(int x, int st[], int n);

int main()
{
int array[6] = {1,2,3,4,5,6};
int findx;

scanf("%d",&findx);

printf("%d\n",bserch(findx,array,6));

return 0;
}

I can't receive the correct answer when I input 1 or 4.But when I
replace the statement "high = mid + 1; " by "high = mid;" the
program run correctly. What's wrong? Do I misunderstand? Or......?

Think about the algorithm. low and high are the lower and upper bounds
of the index which can contain the item being searched. For the case (x
< v[mid]), the correct index must be less than mid, therefore the proper
adjustment is high = mid - 1.

I have K&R1, not K&R2, and is has the proper adjustment in the code
(page 54).

 

[Richard Heathfield]

Tak said:

HI,EVERYONE:
That's my puzzle:
page52 of <The c programming language>(k&r),It writes:
/* 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;

No, it doesn't.

 

[user923005]

Tak said:

HI,EVERYONE:
That's my puzzle:
page52 of <The c programming language>(k&r),It writes:
/* 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;

No, it doesn't.

For the OP...
Here is the world's easiest to understand binary search:

#include <stdlib.h>
void *binsearch(
const void *key,
const void *bbase,
size_t element_count,
size_t element_size,
int (*comp) (const void *, const void *)
)
{
const char *base = bbase;
size_t window;
int cmp;
const void *guess;
/* Start with a window of the full size and halve it each pass */
for (window = element_count; window != 0; window >>= 1) {
/* Examine the middle element of this window */
guess = base + (window >> 1) * element_size;
/* by definition, comp returns -1 for <, 0 for =, +1 for > */
cmp = comp(key, guess);
if (!cmp) /* Did we find it? */
return ((void *) guess);
if (cmp > 0) { /* It's in the other half... */
base = (char *) guess + element_size;
window--;
}
}
return (NULL);
}