Like Tree2Likes
  • 1 Post By whiteflags
  • 1 Post By iMalc

Binary Search Help Repost.

This is a discussion on Binary Search Help Repost. within the C++ Programming forums, part of the General Programming Boards category; I've got the logic right and the algo seems to work fine. Now, that's epic for me But.. I want ...

  1. #1
    Registered User Sid_TheBeginner's Avatar
    Join Date
    Jun 2012
    Location
    India
    Posts
    19

    Cool 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
    Last edited by Sid_TheBeginner; 06-29-2012 at 12:36 AM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,602
    Quote 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.)

    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User Sid_TheBeginner's Avatar
    Join Date
    Jun 2012
    Location
    India
    Posts
    19
    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.
    Last edited by Sid_TheBeginner; 06-29-2012 at 12:45 AM.

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,661
    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.

  5. #5
    Registered User Sid_TheBeginner's Avatar
    Join Date
    Jun 2012
    Location
    India
    Posts
    19
    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

  6. #6
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,661
    // 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.

  7. #7
    Registered User Sid_TheBeginner's Avatar
    Join Date
    Jun 2012
    Location
    India
    Posts
    19
    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

  8. #8
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,661
    Quote Originally Posted by Sid_TheBeginner View Post
    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.

  9. #9
    Registered User Sid_TheBeginner's Avatar
    Join Date
    Jun 2012
    Location
    India
    Posts
    19
    Worked! I've replaced the for with a while loop in the function!
    Thanks,
    --Sid

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by Sid_TheBeginner View Post
    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))
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Registered User
    Join Date
    Mar 2011
    Posts
    406
    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;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree-search method help?
    By shocklightning in forum C++ Programming
    Replies: 5
    Last Post: 03-25-2012, 10:57 PM
  2. Difference Between A Linear Search And Binary Search
    By ImBack92 in forum C Programming
    Replies: 4
    Last Post: 05-12-2011, 08:47 AM
  3. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 01:12 PM
  4. Search Engine - Binary Search Tree
    By Gecko2099 in forum C Programming
    Replies: 9
    Last Post: 04-17-2005, 02:56 PM
  5. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 09:18 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21