Binary Search issues

[Mechennyy]

Hello everyone, I am trying to write a program that uses a binary search to find the position in the array of the element the user picks. I am having two problems.
The first is the output is reversed. The program should show the elements in the array and have the user pick one. It should then output

"userpick" is in position "position of userpick"

Instead what happens is if 6 is the second integer in the array and the user types
6, it shows the 6th element. (If you don't understand exactly what I mean run the code)

The second is that the user should either input one of the elements or x to exit, and I'm not exactly sure how to work that out. I have tried to convert it
to a char but if x is typed the program goes into an infinite loop. But if 120 if typed instead of x it exits.

Thanks

#include <iostream>
#include <string>

using namespace std;

//Global variables
int myArr[23] = { 1, 4, 5, 6, 9, 14, 21, 23, 28, 31, 35, 42, 46, 50, 53, 57, 62, 63, 65, 74, 79, 89, 95 };


//Forward Declarations
int binSearch(int data[], int numElements, int searchKey);

int main()
{
	int answer = 0;
	bool quit = false;

	while (quit == false)
	{
		for (int x = 0; x < 23; ++x)
		{
			cout << myArr[x] << ", ";
		}

		cout << endl;

		cout << "Enter search key (or 'x' to exit) : ";
		cin >> answer;

		char answer2 = (char)answer;

		if (answer2 == 'x')
		{
			cout << "Exiting....." << endl;
			quit = true;
		}

		else
		{
			int result = binSearch(myArr, 23, answer);
			
			cout << myArr[answer] << " is in position " << result << endl;
		}
	}

	cout << endl;
	system("Pause");
}

int binSearch(int data[], int numElements, int searchKey)
{
	int low = 0;
	int high = numElements - 1;

	while (low <= high)
	{
		int mid = (low + high) / 2;
		
		if (mid == searchKey)
			return mid;

		else if (mid < searchKey)
			low = mid + 1;

		else 
			high = mid - 1;
	}

	return 1;
}

[long double main]

First of all, you can just put myArr inside main -- it doesn't need to be a global variable, and your code will still work just fine. (The reason is that you're already passing myArr as a parameter to the function, so you don't need to make myArr global.)

Now...

int result = binSearch(myArr, 23, answer);

cout << myArr[answer] << " is in position " << result << endl;

Since the number you're looking for is answer, the cout statement on line 42 should just be
cout << answer << " is in position " << result << endl;.

Now, for your actual binary search algorithm:

if (mid == searchKey)
    return mid;

else if (mid < searchKey)
    low = mid + 1;

Here, you're comparing the index mid to the value you're searching for (searchKey).
What you probably intended to do was compare the element at index mid with searchKey:

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

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

And on a side note, the code you use to check if the user wants to quit doesn't quite work:

cout << "Enter search key (or 'x' to exit) : ";
cin >> answer;

char answer2 = (char)answer;

if (answer2 == 'x')
{
    cout << "Exiting....." << endl;
    quit = true;
}

Line 30 will just take the integer value that's stored in answer (remember, ints can't hold anything other than integers, so if you enter a character, it won't "store" it for you in case you wanted to check what the user actually entered) and convert it to a char, which will likely be the character whose ASCII value is equal to the number you entered. (For kicks, try entering "120" and see what happens.)

If you want to check whether the user entered a character, you can do something like this:

cout << "Enter search key (or 'x' to exit) : ";
if (!(cin >> answer)) // If the input failed, e.g. if you entered a character
{
    cout << "Exiting....." << endl;
    quit = true;
}

Now, this will exit if you enter any non-digit character as the first character.
If you want it to exit only when the user enters "x", that's (slightly) more complicated....

Instead, I would suggest that you make the program exit when the user enters something like -1, which is much easier to check for than a character like "x":

cout << "Enter search key (or -1 to exit) : ";
cin >> answer;

if (answer == -1)
{
    cout << "Exiting....." << endl;
    quit = true;
}

700!

[Mechennyy]

Thanks.

Although now for some reason I have to type the element to search for twice. If I input 6 it goes to a new line and waits for me to type 6 again before the program continues. Also if I input 6 and then 14, it will show the position of 14. I only have to input x once though.

[giblit]

Can you show us the code you have? Also in your binary search you probably meant to return -1 if no items were found and not 1. If you return 1 that could be mixed up with it being found at index 1.

[Mechennyy]

I meant to but forget to post it.

#include <iostream>
#include <string>

using namespace std;


//Forward Declarations
int binSearch(int data[], int numElements, int searchKey);

int main()
{
	int myArr[23] = { 1, 4, 5, 6, 9, 14, 21, 23, 28, 31, 35, 42, 46, 50, 53, 57, 62, 63, 65, 74, 79, 89, 95 };
	int answer = 0;
	bool quit = false;

	while (quit == false)
	{
		for (int x = 0; x < 23; ++x)
		{
			cout << myArr[x] << ", ";
		}

		cout << endl;

		cout << "Enter search key (or 'x' to exit) : ";
		cin >> answer;

		if (!(cin >> answer))//if input failed *input character instead of integer*
		{
			cout << "Exiting....." << endl;
			quit = true;
		}

		else
		{
			int result = binSearch(myArr, 23, answer);
			
			cout << answer << " is in position " << result << endl;
		}
	}

	cout << endl;
	system("Pause");
}

int binSearch(int data[], int numElements, int searchKey)
{
	int low = 0;
	int high = numElements - 1;

	while (low <= high)
	{
		int mid = (low + high) / 2;
		
		if (data[mid] == searchKey)
			return mid;

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

		else 
			high = mid - 1;
	}

	return -1;
}

[giblit]

remove line 26.

[Mechennyy]

Thanks, but how exactly does it work without it? It would seem like lines 28 and 34 would just check what the input was instead of assigning.

[giblit]

well line 28 read in cin >> answer; If you didn't know operator >> returns a std::istream & and that is why you can chain it. so when we put parenthesis around it we get the last std::istream & which would be what is returned after reading into answer. Then we use operator ! on it which returns true if the failbit or badbit are set. http://www.cplusplus.com/reference/ios/ios/operator_not/
http://www.cplusplus.com/reference/istream/istream/operator%3E%3E/

[Mechennyy]

Thanks guys.

Learning C++ is going to be a slow and painful process.