Binary Search Help Repost.

I've got the logic right and the algo seems to work fine. Now, that's epic for me
But..

I want to add 2 more features to this code:

1) Exit on pressing 'x'. For now I'm using -1 to exit.
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 :|
Well, Here goes my code:

Code:

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);
    
    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;
        }
    }
    


}

Thanks,
--Sid

Originally Posted by Sid_TheBeginner

1) Exit on pressing 'x'. For now I'm using -1 to exit.

You should read the input into a string then. If the input matches "x", exit, otherwise parse the string into an int. (A stringstream can help.)

Originally Posted by Sid_TheBeginner

2) Print a message "Element not found" when an element not present in the array is searched for.

Start by changing BinSearch to account for the possibility that the searchKey is not in data. Actually, it looks like you already test for searchKey == -1 in main, so you could just change the resulting message, but BinSearch does not actually return -1.

Thanks for your reply! I'm now returning -1 outside the for loop in the BinSearch function but I'm not able to figure out how to print a message using that return value -1 And stringstream hasn't been introduced yet in the book I'm following. At this point, I'm familiar with loops, switch statement, functions and arrays.

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

Originally Posted by Sid_TheBeginner

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

Very good. I've been waiting to see if you would figure that out. I assume you've removed the variable 'i' now then?

If your input that exits doesn't necessarily have to be an x, just some non-integer, then the following should be okay:

Code:

    if (!(cin >> searchKey))

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;
}