Binary Search Help.

[Sid TheBeginner]

I've got the logic right and the algo seems to work fine. Now, that's epic for me :D 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:

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

}

Thanks,
--Sid

[TheIdeasMan]

Hi Sid TheBeginner,

This is generally a bad idea


for(;;)

This is better:

char QuitValue = 'a'; //purposely initialised to something invalid
while (QuitValue != 'x') {
//do stuff

}

you might have to ask a separate question about quitting as well as getting the search key.

[Sid TheBeginner]

Hey TheIdeasMan,
Thanks for stopping by..

I got it running here it is .But....

It goes on asking for a value until -1 is typed in. I want to exit using 'x' Can you help me with that?

#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.
	while(beg <= 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

[TheIdeasMan]

Sid

The answer to your question was the purpose of my last post:

char QuitValue = 'a'; //purposely initialised to something invalid
while (QuitValue != 'x') {
//do stuff

}

and this

you might have to ask a separate question about quitting as well as getting the search key.

Was the other clue.

Another clue is that you put questions about the search key and quitting inside the while loop I gave you .