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! 3 1532
Tak wrote:
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).
--
Thad
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.
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
On Oct 10, 1:17 am, Richard Heathfield <r...@see.sig.invalidwrote:
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);
} This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Collin VanDyck |
last post by:
I have a basic understanding of this, so forgive me if I am overly
simplistic in my explanation of my problem..
I am trying to get a Java/Xalan transform to pass through a numeric
character...
|
by: Philipp Lenssen |
last post by:
I don't know the English word, but I'm referring to the double-dash
which is used to separate parts of a sentence. I'm using so far.
Now I saw – which is slightly shorter. Some sites use --.
...
|
by: BoonHead, The Lost Philosopher |
last post by:
I think the .NET framework is great!
It's nice, clean and logical; in contradiction to the old Microsoft.
It only saddens me that the new Microsoft still doesn't under stand there own...
|
by: BigMan |
last post by:
Does the C++ standard say anything about how arithmetic exceptions
(such as integer division by 0) interfere with C++ exceptions? I see
that catch clauses DO catch arithmetic exceptions but...
|
by: Alex Fraser |
last post by:
From searching Google Groups, I understand that void pointer arithmetic is a
constraint violation, which is understandable. However, generic functions
like qsort() and bsearch() must in essence do...
|
by: Daniel Vallstrom |
last post by:
I'm having problems with inconsistent floating point behavior
resulting in e.g.
assert( x > 0.0 && putchar('\n') && x == 0.0 );
holding. (Actually, my problem is the dual one where I get...
|
by: Bill Reid |
last post by:
Bear with me, as I am not a "professional" programmer, but I was
working on part of program that reads parts of four text files into
a buffer which I re-allocate the size as I read each file. I...
|
by: Robin Becker |
last post by:
Hi, just trying to avoid wheel reinvention. I have need of an unsigned 32 bit
arithmetic type to carry out a checksum operation and wondered if anyone had
already defined such a beast.
Our...
|
by: GCRhoads |
last post by:
I'm looking for a very basic high-precision arithmetic library. I
need to be able to specify a fixed number of bits or decimal digits
(32 decimal digits should be all I need). The only arithmetic...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
| |