Thread: Binary Search Help Repost.

Like you wrote an if statement for binary search, you will need one for the return value of binary search if you want to do anything after a failed search.

As for ending the program with x: currently you ask the user for integers which are searchKeys. One idea is to keep asking for searchKeys, but eventually that will stop working because x is not a number. So you will have to check the stream state every time. Then you have to clear() the stream when it goes bad and read your x. If your book doesn't explain how to check the stream state or the clear() function to you, learn those anyway. It's actually the only other way I can think of that doesn't involve a lot of crazy work, and for what it's worth, the knowledge is good for you anyway.

Thanks for the reply.
Can you please look at this code and let me know?

Code:

#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[i] << ", ";
	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;
}

Thanks,
--Sid

// I want to quit when I press 'x'. Please let me know.

I tried to explain the x thing. If your book really wants you to do that it should have talked about testing the state of cin somewhere. I've gone through a couple books myself and they all talk about validating inputs. That's what you need to do to do this. Think about it.

Enter search key: (x to exit) 1
Enter search key: (x to exit) 22
Enter search key: (x to exit) 333

... Everything is going good until:

Enter search key: (x to exit) x

When the user stops typing integers, the idea is that the read for the next integer will fail and put the stream into a bad state. You need to clear() the stream and read the x that you are expecting. Check what you read and if it is x, end the program. I hope that is helpful.

In the above code I posted, I'm not able to print "Not FOund" when a number not present in the array is tried for... And could you please post the syntax for how to clear the stream?
Thanks,
--Sid

Originally Posted by Sid_TheBeginner

In the above code I posted, I'm not able to print "Not FOund" when a number not present in the array is tried for...

Looking at it, it seems like the loop in binSearch goes on forever and no one noticed until now.

And could you please post the syntax for how to clear the stream?
Thanks,
--Sid

I have. clear(). Call clear() on the stream like any other object member function.

Worked! I've replaced the for with a while loop in the function!
Thanks,
--Sid

Would it be possible to to use ungetchar() or ungetc() to return the character to the input stream after testing
for equal to 'x', and then use cin for the searchKey?

for example:

Code:

if (getchar() == 'x')
   code here for exiting;
else
{   ungetchar();
    cin >> searchKey;
}