Thread: Need some more help

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    44

    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. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Nov 2008
    Posts
    44
    oh ok ill try to redo it, but what about the "x" thing to exit? how do i do that?

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Nov 2008
    Posts
    44
    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. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed