Is this binary search correct

[Kiko Tores]

If there is something wrong , could you please point it out ( if you
can give me an example as well)

int find( int array[], int size, int key )
{
int begin=0, end=size-1, middle;
while (end>begin){

middle = (begin+end) /2;
if (key>array[middle])
begin=middle+1;
else
end = middle;
}

if (key==array[end]) return end;


return -1;
}

 

[Victor Bazarov]

If there is something wrong , could you please point it out ( if you
can give me an example as well)

int find( int array[], int size, int key )
{
int begin=0, end=size-1, middle;
while (end>begin){

middle = (begin+end) /2;
if (key>array[middle])
begin=middle+1;
else

You could probably shorten your search if you add the equality comparison

if (key == array[middle])
return middle;
else

but it's not necessarily so because time is spent comparing too. So, it
will depend on the contents of the 'array'. If on average it _does_ have
the value you're looking for, then probably adding the == will help. If
it does not, it will delay the decision a bit.

end = middle;
}

if (key==array[end]) return end;


return -1;
}

V

 

[kikotores]

but there is no way the loop is gonna be infinite right. cuz thats what
i was told by my professor

If there is something wrong , could you please point it out ( if you
can give me an example as well)

int find( int array[], int size, int key )
{
int begin=0, end=size-1, middle;
while (end>begin){

middle = (begin+end) /2;
if (key>array[middle])
begin=middle+1;
else

You could probably shorten your search if you add the equality comparison

if (key == array[middle])
return middle;
else

but it's not necessarily so because time is spent comparing too. So, it
will depend on the contents of the 'array'. If on average it _does_ have
the value you're looking for, then probably adding the == will help. If
it does not, it will delay the decision a bit.

end = middle;
}

if (key==array[end]) return end;


return -1;
}

V

 

[Stephan Keil]

but there is no way the loop is gonna be infinite right. cuz thats what

i was told by my professor

I see no problem with your code (except that for size<=0 it is
undefined). Maybe your prof can post a counter-example here

- Stephan

 

[Victor Bazarov]

but there is no way the loop is gonna be infinite right. cuz thats what
i was told by my professor

Perhaps he didn't see the '+1' in the assignment to 'begin'...

I don't see how it can be. The questionable situation is when only
1 separates 'begin' and 'end'. In that case middle==begin, and you
can get an infinite loop if you do 'begin = middle'. But you do
'begin = middle + 1' or 'end = middle', thus _always_ shrinking the
searched interval. Eventually 'end == begin' and the 'while' loop
finishes (since it only goes on if 'end' and 'begin' are different.

Now, your code does have _undefined_behaviour_ which I didn't see at
the first time. Imagine that size==1. In that case begin==end and is
0. The loop skips, and the following statement executes:

if (key == array[middle]) ...

but 'middle' hasn't been initialised to anything. So, you dereference
a pointer that _can_ easily be invalid. You need to initialise the
'middle' variable to 0.

What happens if somebody passes 'size' as a negative number? If 'size'
is not INT_MIN, then the loop skips again and you only check the 0-th
element (assuming 'middle' was initialised to 0). If, beyond all hope,
somebody does pass INT_MIN as 'size', then you are in trouble because
you try to calculate 'end' based on that and you get _int overflow_ if
you subtract 1 from INT_MIN. That's undefined behaviour too, IIRC.

I'd check 'size' for being negative and returned -1 in that case.

You know, if I were you, I'd play a fool and ask your professor how the
infinite loop happens. Let your professor explain to you. If it's really
an infinite loop, post it here to my shame. If it's not, your professor
should see it and admit his/her mistake.

If there is something wrong , could you please point it out ( if

you

can give me an example as well)

int find( int array[], int size, int key )
{
int begin=0, end=size-1, middle;
while (end>begin){

middle = (begin+end) /2;
if (key>array[middle])
begin=middle+1;
else

You could probably shorten your search if you add the equality
comparison

if (key == array[middle])
return middle;
else

but it's not necessarily so because time is spent comparing too. So,
it

will depend on the contents of the 'array'. If on average it _does_
have

the value you're looking for, then probably adding the == will help.
If

it does not, it will delay the decision a bit.

end = middle;
}

if (key==array[end]) return end;


return -1;
}

V

 

[Stephan Keil]

Now, your code does have _undefined_behaviour_ which I didn't see at

the first time. Imagine that size==1. In that case begin==end and is
0. The loop skips, and the following statement executes:

if (key == array[middle]) ...

In the original code this line reads
if (key==array[end]) return end;
so no problem here with size==1.

 

[kikotores]

yup yup

if (key == array[middle]) ...

In the original code this line reads
if (key==array[end]) return end;
so no problem here with size==1.

I can put some error checking against nastiness like putting size<=0
put the point is in the algorithm itself and I think this time my prof
has made a mistake )
I m gonna talk to him today and let you know whats his final statement

 

[kikotores]

yup he admitted he overlooked that the last if was outside the loop
so this was all in vain )))

 

[kikotores]

yup he admitted he overlooked that the last if was outside the loop
so this was all in vain )))

 

[Karl Heinz Buchegger]

yup he admitted he overlooked that the last if was outside the loop
so this was all in vain )))

Look again at your original post.
Does it look exactly the same way as the one you presented
to him. If yes: no wonder he missed that, your indentation
is completely fooled up. Now you know why consistent indentation
is a valuable thing.

If your newsreader messed up the code during posting, please
ignore the above, it wasn't your fault then.

 

[kikotores]

well the indentation here is really different than the one I sent him
but now i saw that the if was really wrongly indented. Yup , thats why
some professors take off points for improper indentaion
thanks though ))