Velocity Reviews > Binary Search

# Binary Search

willamette3597@gmail.com
Guest
Posts: n/a

 10-30-2005
Could Someone tell me Where can I get The result though the Binary
Search
eg.
max , min , mid ,want;
While ( max > min )
{
mid = (min + max )/2 ;
if ( mid > want ) max = mid + 1;
else min = mid -1 ;
Line1 :
}
Line2 :
Where can I get the correct result ? Line1 or Line2 ?

Sandeep
Guest
Posts: n/a

 10-30-2005
>>Could Someone tell me Where can I get The result though the Binary
>>Search
>>eg.
>>max , min , mid ,want;
>>While ( max > min )
>>{
>>mid = (min + max )/2 ;
>>if ( mid > want ) max = mid + 1;
>>else min = mid -1 ;
>>Line1 :
>>}

>>Line2 :
>>Where can I get the correct result ? Line1 or Line2 ?

The best way to answer these questions is to take a sample ( an array
and a key in this case ), and then run through your algorithm/code for
both positive and negative cases.

Norm Mann
Guest
Posts: n/a

 10-31-2005

"Sandeep" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...
>>>Could Someone tell me Where can I get The result though the Binary
>>>Search
>>>eg.
>>>max , min , mid ,want;
>>>While ( max > min )
>>>{
>>>mid = (min + max )/2 ;
>>>if ( mid > want ) max = mid + 1;
>>>else min = mid -1 ;
>>>Line1 :
>>>}

>
>>>Line2 :
>>>Where can I get the correct result ? Line1 or Line2 ?

>
> The best way to answer these questions is to take a sample ( an array
> and a key in this case ), and then run through your algorithm/code for
> both positive and negative cases.
>

I agree the best way is to run through the program and see how it behaves,
but I also think one needs to understand the principle of the algorithm one
is trying to implement.
There are actually two "correct" results: "match" and "no match".
"Match" is where "DATA(mid) = want" and usually results in exiting from the
while loop before the default termination. ("max", "mid" and "min" are
usually pointers or indexes.)
"No match" is where the while loop terminates when "max" <= "min".
This sample routine doesn't even check for a match and if one looks at the
way "min" and "max" are updated, it may result in an endless loop as it
narrows the search to a few data entries. If it were working correctly,
"mid" would be a place to insert "want", if no match was found or it points
to where "want" is, if a match is found.

HTH,

-NM