Re: [C++] Binary Search Confusion
From: Karl Heinz Buchegger (kbuchegg_at_gascad.at)
Date: 03/18/04
- Next message: Curley Q.: "Re: [C] printf & unsigned long long"
- Previous message: Legion: "Re: [C++] Binary Search Confusion"
- In reply to: Legion: "Re: [C++] Binary Search Confusion"
- Next in thread: Legion: "Re: [C++] Binary Search Confusion SOLVED!"
- Reply: Legion: "Re: [C++] Binary Search Confusion SOLVED!"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Thu, 18 Mar 2004 15:30:42 +0100
Legion wrote:
>
> Woops, i'm sorry I failed to mention.. I have another function which sorts
> all the information (bubble sort) once all the information is entered. I'll
> elaborate a little more.
>
> I have the program ask for 15 numbers from the user, they enter the 15
> numbers, then the array which stores those numbers is bubble sorted (in
> order from lowest at the beginning of the array, to largest at the bottom of
> the array). Then after that the user is prompted to enter a number to search
> for, which this is taken into the binary search function. Regardless, in the
> binary search function, what is not making sense to me, is how array[middle]
> is becomming a value of 1 instead of the expected 7.
Hmm. Your explanation doesn't make much sense to me. array[middle] shouldn't
change it's value at all. middle does change in value, but not the array.
Hmm.
Let's try this with specific numbers.
Say the user enters
18 15 13 20 14 8 2 10 12 55 78 34 24 37 1
You then sort them
1 2 8 10 12 13 14 15 18 20 24 34 37 55 78
Then the user asks to search for eg. 12
you call the function
> int binarySearch(const int array[], int searchKey, int low, int high, int size)
> {
> int middle;
>
> while (low <= high)
> {
> middle = (low + high) / 2;
>
> if ( searchKey == array[ middle ] )
> return middle;
>
> else if ( searchKey < array[ middle ] )
> high = middle - 1;
>
> else
> low = middle + 1;
> }
>
> return -1;
> }
as this:
binarySearch( array, 12, 0, 14, 15 )
and the function does:
while( low <= high )
{
low == 0, high == 14: low <= high -> true, while loop continues
middle = (low + high) / 2;
middle = ( 0 + 14 ) / 2 -> 7
if ( searchKey == array[ middle ] )
array[7] == 15, searchkey == 12: not equal
else if ( searchKey < array[ middle ] )
array[7] == 15, searchkey == 12: is less -> then part is taken
high = middle - 1;
high gets new value of 7 - 1 -> 6
while( low <= high )
{
low == 0, high == 6: low <= high -> true, while loop continues
middle = (low + high) / 2;
middle = ( 0 + 6 ) / 2 -> 3
if ( searchKey == array[ middle ] )
array[3] == 10, searchkey == 12: not equal
else if ( searchKey < array[ middle ] )
array[3] == 10, searchkey == 12: is not less
else
low = middle + 1;
low gets new value of 3 + 1 -> 4
while( low <= high )
{
low == 4, high == 6: low <= high -> true, while loop continues
middle = (low + high) / 2;
middle = ( 4 + 6 ) / 2 -> 5
if ( searchKey == array[ middle ] )
array[5] == 13, searchkey == 12: not equal
else if ( searchKey < array[ middle ] )
array[5] == 13, searchkey == 12: is less -> then part taken
high = middle - 1;
high gets a new value of 5 - 1 -> 4
while( low <= high )
{
low == 4, high == 4: low <= high -> true, while loop continues
middle = (low + high) / 2;
middle = ( 4 + 4 ) / 2 -> 4
if ( searchKey == array[ middle ] )
array[4] == 12, searchkey == 12: equal -> then part taken
return middle;
and finally your function returns 4, which is the position of 12
in the array.
Try to reproduce that paper analysis with your function and look at every
step and all variables involved in that step with your debugger.
You should see the exact same numbers as I have written them down in the
above.
If that doesn't help yourself to find the problem, then pleast post a
complete, compilable program which demonstrates the error. Replace the
user input with some fixed numbers if you do want to do us a favour. This
way we have the exact same program with the exact same numbers as you have.
Somebody (maybe me) will take a look at it and figure out what's wrong.
-- Karl Heinz Buchegger kbuchegg@gascad.at
- Next message: Curley Q.: "Re: [C] printf & unsigned long long"
- Previous message: Legion: "Re: [C++] Binary Search Confusion"
- In reply to: Legion: "Re: [C++] Binary Search Confusion"
- Next in thread: Legion: "Re: [C++] Binary Search Confusion SOLVED!"
- Reply: Legion: "Re: [C++] Binary Search Confusion SOLVED!"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
