Jump to content
  • Advertisement
Sign in to follow this  

Binary Search Help Repost.

This topic is 2151 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

[color=#000000][font=verdana, arial, helvetica, sans-serif]

I've got the logic right and the algo seems to work fine. Now, that's epic for me biggrin.png But..[/font]

[color=#000000][font=verdana, arial, helvetica, sans-serif]

I want to add 2 more features to this code:[/font]

[color=#000000][font=verdana, arial, helvetica, sans-serif]

1) Exit on pressing 'x'. For now I'm using -1 to exit.[/font]
[color=#000000][font=verdana, arial, helvetica, sans-serif]

2) Print a message "Element not found" when an element not present in the array is searched for. Yeah, I'm not able to figure that out :|[/font]
[color=#000000][font=verdana, arial, helvetica, sans-serif]

Well, Here goes my code:[/font]

[font=verdana, arial, helvetica, sans-serif][color=#000000]

[/font]

#include<iostream>
using namespace std;

int BinSearch(int data[], int numElements, int searchKey); // Prototype

int main()
{
int data[] = {1, 4, 5, 6, 9, 14, 21, 23, 28, 31, 35, 42, 46, 50, 53, 57, 62, 63, 65, 74, 79, 89, 95};
int numElements = 23; // Size of the Array is 23!!!
int searchKey;
int found;

for(int i = 0; i < numElements; i++)
cout << data << ", ";
cout << endl;

for(;;)
{
cout << "Enter search key: (-1 to exit) "; // I want to quit when I press 'x'. Please let me know.
cin >> searchKey;

if(searchKey == -1)
{
cout << "Exiting\n";
break;
}

found = BinSearch(data, numElements,searchKey);

cout << searchKey << " is in position " << found << endl;
}

}

int BinSearch(int data[], int numElements, int searchKey)
{
int position, mid;
int beg = 0;
int end = numElements;

// Algorithm Begins.
for(int i = beg; i <= end;)
{
mid = (beg+end)/2;

if(data[mid] == searchKey)
{
return mid;
}
else if(data[mid] > searchKey)
{
end = mid - 1;
}
else if(data[mid] < searchKey)
{
beg = mid + 1;
}
}

}

[font=verdana, arial, helvetica, sans-serif][color=#000000]

[/font]
Thanks,
--Sid Edited by Sid_TheBeginner

Share this post


Link to post
Share on other sites
Advertisement
Didn't the compiler give you a warning message something about [font=verdana, arial, helvetica, sans-serif][color=#000000]

BinSearch[/font] not returning a value? Because it's only returning a value, when it's found the element. Hmm.

What does it return when it finds the element? In what range? Hmm. It returns a zero or positive value.

Hmm. That means negative values aren't used. Hmm.

That means we could use negative values for other purposes, such as indication that the element is not used? Yay! Let's use -1 for indicating that no element is found (that's pretty standard).
We could even use more negative numbers for other error codes, such as the input numElements was negative... That's another story.

But how can we decide if the element is not found? Wait. We already see that the [font=verdana, arial, helvetica, sans-serif][color=#000000]

BinSearch[/font] is only returning a value when it's found something. If it doesn't return, then what happens? Hmmm.
We get to the end of the for loop!

So we know we have to return -1 when nothing is found, and we know that we arrive after the for loop when nothing is found.

Let's put a return -1 after the for loop then!

Yay! We have signalled that we haven't found the element, and we can act upon it by checking the return value of [font=verdana, arial, helvetica, sans-serif][color=#000000]

BinSearch[/font] in Main.
Hmm, that also means we successfully decoupled the logic from the input/output.

In this particular program, we can print stuff differently depending on the return value. If it's -1, we print "nothing found". If it's >= 0, we print the value. Edited by szecs

Share this post


Link to post
Share on other sites
@szecs Hey, thanks for your replyl!

Do you mean this:


#include<iostream>
using namespace std;

int BinSearch(int data[], int numElements, int searchKey); // Prototype

int main()
{
int data[] = {1, 4, 5, 6, 9, 14, 21, 23, 28, 31, 35, 42, 46, 50, 53, 57, 62, 63, 65, 74, 79, 89, 95};
int numElements = 23; // Size of the Array is 23!!!
int searchKey;
int found;

for(int i = 0; i < numElements; i++)
cout << data << ", ";
cout << endl;

for(;;)
{
cout << "Enter search key: (-1 to exit) "; // I want to quit when I press 'x'. Please let me know.
cin >> searchKey;

if(searchKey == -1)
{
cout << "Exiting\n";
break;
}

found = BinSearch(data, numElements,searchKey);

if(found == -1)
cout << searchKey << " not found\n";

cout << searchKey << " is in position " << found << endl;
}

}

int BinSearch(int data[], int numElements, int searchKey)
{
int mid;
int beg = 0;
int end = numElements;
bool not_found = 1;

// Algorithm Begins.
for(int i = beg; i <= end;)
{
mid = (beg+end)/2;

if(data[mid] == searchKey)
return mid;

else if(data[mid] > searchKey)
end = mid - 1;

else if(data[mid] < searchKey)
beg = mid + 1;

else
return -1;
}


}


This doesn't seem to work. Sorry, I didn't completely understand what you meant...

And Yea, the compiler's telling me this:
warning C4715: 'BinSearch' : not all control paths return a value Edited by Sid_TheBeginner

Share this post


Link to post
Share on other sites
No. I didn't mean that. Just think over what I said in my first post.
"End of for loop" may be misworded. I meant "after the for loop".

The complier says not all control paths return a value. Can you figure out what path doesn't return in your code?
With your modifications the code still produces this warning message so that means you didn1t insert the return -1 where I implied.

And think about it: what control path doesn't return value? The path that doesn't find the value. Just debug it on paper. That is the exact point where you have to insert the return -1.


Maybe my English sucks, but I think this should be clear.

And please pay attention to warning messages. Edited by szecs

Share this post


Link to post
Share on other sites
Thanks! No more warnings now. I'm returning -1 outside the for loop in the BinSearch function smile.png
But how do I print a message like "Element not found" using that return value -1 ??

Your English doesn't suck, I'm pure rookie biggrin.png

Share this post


Link to post
Share on other sites
Some spoonfeeding:

found = BinSearch(data, numElements,searchKey);

if( found == -1 )
{
cout << Element not found << endl;
}
else // if( found >= 0 ) // for other error codes
{
cout << searchKey << " is in position " << found << endl;
}
Edited by szecs

Share this post


Link to post
Share on other sites

Some spoonfeeding:

found = BinSearch(data, numElements,searchKey);

if( found == -1 )
{
cout << Element not found << endl;
}
else // if( found >= 0 ) // for other error codes
{
cout << searchKey << " is in position " << found << endl;
}



Thanks for replying. Did You mean this:



#include<iostream>
using namespace std;

int BinSearch(int data[], int numElements, int searchKey); // Prototype

int main()
{
int data[] = {1, 4, 5, 6, 9, 14, 21, 23, 28, 31, 35, 42, 46, 50, 53, 57, 62, 63, 65, 74, 79, 89, 95};
int numElements = 23; // Size of the Array is 23!!!
int searchKey;
int found;

for(int i = 0; i < numElements; i++)
cout << data << ", ";
cout << endl;

for(;;)
{
cout << "Enter search key: (-1 to exit) "; // I want to quit when I press 'x'. Please let me know.
cin >> searchKey;

if(searchKey == -1)
{
cout << "Exiting\n";
break;
}

found = BinSearch(data, numElements,searchKey);

if(found == -1)
cout << "Not Found!\n";

else cout << searchKey << " is in position " << found << endl;
}

}

int BinSearch(int data[], int numElements, int searchKey)
{
int mid;
int beg = 0;
int end = numElements;

// Algorithm Begins.
for(int i = beg; i <= end;)
{
mid = (beg+end)/2;

if(data[mid] == searchKey)
return mid;

else if(data[mid] > searchKey)
end = mid - 1;

else if(data[mid] < searchKey)
beg = mid + 1;
}
return -1;
}


Not working. sad.png Edited by Sid_TheBeginner

Share this post


Link to post
Share on other sites

@szecs Hey, thanks for your replyl!

Do you mean this:


#include<iostream>
using namespace std;

int BinSearch(int data[], int numElements, int searchKey); // Prototype

int main()
{
int data[] = {1, 4, 5, 6, 9, 14, 21, 23, 28, 31, 35, 42, 46, 50, 53, 57, 62, 63, 65, 74, 79, 89, 95};
int numElements = 23; // Size of the Array is 23!!!
int searchKey;
int found;

for(int i = 0; i < numElements; i++)
cout << data << ", ";
cout << endl;

for(;;)
{
cout << "Enter search key: (-1 to exit) "; // I want to quit when I press 'x'. Please let me know.
cin >> searchKey;

if(searchKey == -1)
{
cout << "Exiting\n";
break;
}

found = BinSearch(data, numElements,searchKey);

if(found == -1)
cout << searchKey << " not found\n";

else cout << searchKey << " is in position " << found << endl;
}

}

int BinSearch(int data[], int numElements, int searchKey)
{
int mid;
int beg = 0;
int end = numElements;
bool not_found = 1;

// Algorithm Begins.
for(int i = beg; i <= end;)
{
mid = (beg+end)/2;

if(data[mid] == searchKey)
return mid;

else if(data[mid] > searchKey)
end = mid - 1;

else if(data[mid] < searchKey)
beg = mid + 1;
}

return -1;

}


This doesn't seem to work. Sorry, I didn't completely understand what you meant...

And Yea, the compiler's telling me this:
warning C4715: 'BinSearch' : not all control paths return a value
Edited by Sid_TheBeginner

Share this post


Link to post
Share on other sites
What doesn't work?
Doesn't print stuff? Doesn't print the right value? Never prints "not found"?

What are we debugging here actually??

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!