# Thread: Need some more help

1. ## Need some more help

Sorry for asking so much, but im doing lots of excersises and im having trouble with some things.
Now im doing a script with a Binary search function. But im having trouble with 2 things:
-I dont know how to know if the searchKey entered isnt in the given array.
-Im having trouble with the exiting, since sk is and int and "x" should be a char or a string. So if i initialize sk as a string, how can i convert it to an int?

Here's the script for you to understan what im talking about:

Code:
#include <iostream>
#include <cmath>

using namespace std;

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

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};
cout << "{";
for(int i=0; i<23; i++)
{
if(i != 0)
{
cout << ", ";
}
cout << data[i];
}
cout << "}" << endl;

int sk = 0;
while(sk != 'x' && sk != 'X')
{
cout << "Enter the search key (or \"x\" to exit): ";
cin >> sk;

cout << sk << " is in position " << BinSearch(data,23,sk) << endl;
}
cout << "Exiting..." << endl;
system("PAUSE");
}

int BinSearch(int data[], int numElements, int searchKey)
{
int mid = ceilf((float)numElements/2);
int result = 0;
while(true)
{
if(searchKey == data[mid])
{
result = mid;
break;
}
else if(searchKey > data[mid])
{
if(mid % 2 == 0)
{
mid += mid/2;
}
else
{
mid += ceilf((float)mid/2);
}
}
else if(searchKey < data[mid])
{
if(mid % 2 == 0)
{
mid -= mid/2;
}
else
{
mid -= ceilf((float)mid/2);
}
}
}
return result;
}

2. Generally, you shouldn't use floating point calculations in a binary search. I usually use a "low / high" method, where you start with low = 0 (or wherever the start of the actual data is) and high = numElements - 1.
The point you look at (mid) is then calculated as "mid = (high + low) / 2". Then compare the mid-point item with the key. If it's a match, you've found it. If it's the key is smaller, move the high to mid-1, if it's the key is bigger, move low to mid+1. Keep going until found or high is smaller than low (= not found).

--
Mats

3. oh ok ill try to redo it, but what about the "x" thing to exit? how do i do that?

4. So, 'X' is not a number, so won't be accepted by "cin >> sk" if sk is declared as an integer. Using a temporary string, and if the string is not "X" or "x", then convert the string to a number. Or use an unusual integer value (e.g. -1) to exit will also work. I'd go for the latter if you haven't got a VERY good reason to use a string.

Of course, as you get more advanced, I'm sure you'll want to have "idiot safe input", and that will mean reading a string, because if someone enters "abc" in the input, it will fail and get stuck in your current code. But if it's not part of your project to be "idiot safe input", then a "special" value is a much easier and equally good solution.

--
Mats

5. i havent got a very good reason for using x, but the excersise says so, and im trying to learn, so id like to use a letter, since i already know how to do it with "-1". so i have one more question, how do i covert a string into a number?

6. Use a stringstream - that's C++'s corresponding to sscanf/sprintf.

something like this (assumg "str" is a string containing your input):
Code:
// with other include lines:
#include <sstream>
...

stringstream ss;
ss << str;
if (!ss >> sk)
// error happened; write "bad input" or some such.
else
// use sk  to search for.
--
Mats