Thread: binary search algorithm problem...

  1. #1
    Registered User
    Join Date
    Nov 2001
    Posts
    255

    binary search algorithm problem...

    ok for school im literally copy and pasting the binary search algorithm he gave us and apparently went i showed him my flowchart before i coded this program we musta missed something because it always returns a -1 and its due tommorrow and since i copy and pasted the algorithm well just used the already made one i have NO CLUE why its not working since it matches the flowchart just beautiful at least im not noticing an error

    anyway why does it always return -1


    Code:
    int bin_search(int id[],int elementsize,int user_id)
    {
    	cout <<"BEGIINUIG";
    	int first = 0;
    	int last = elementsize -1;
    	int found = 0;
    	int mid;
    	while(first <= last && found == 0)
    	{
    		mid = (first + last) / 2;
    		if(id[mid] == user_id)
    			found = 1;
    		else 
    		{
    			if(id[mid] < user_id)
    				last = mid - 1;
    			else
    				first = mid + 1;
    		}
    	}
    		if(found == 0)
    	{
    		cout << "ALMOST THERE";
    		mid = -1;
    	}
    	
    	cout << "ENDING";
    	return mid;
    }
    hooch

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    anyway why does it always return -1
    Code:
    if(found == 0)
    {
    cout << "ALMOST THERE";
    mid = -1;
    }
    BTW work on proper indentation

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> BTW work on proper indentation

    The forum editor often screws up indentation.

  4. #4
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    put some numbers into your algo and you will see the problem immediately
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  5. #5
    Registered User
    Join Date
    Nov 2001
    Posts
    255
    but shouldnt found = 1 if it finds it so then found should never = 0 to assign mid -1? at least thats how i saw it?


    and yea the forum editor messed up indention
    hooch

  6. #6
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Quote Originally Posted by Daved
    >> BTW work on proper indentation

    The forum editor often screws up indentation.
    Only if you use tabs instead of spaces

  7. #7
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    say u have 0-1000 in a sorted array. try to find 20. follow your code thru and see what happens.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> Only if you use tabs instead of spaces

    Don't mean to derail the thread, but while ssjnamek is following the code to see what is wrong, I'll say that the editor messes up spaces as well (at least the WYSIWYG editor).

  9. #9
    Registered User
    Join Date
    Nov 2001
    Posts
    255
    ok i see that it seems to increase instead of chop in half. although i have no clue why its increasing instead of chopping.

    well i see why its doing it cause first and last arent changing but by + or - 1 to mid and then just getting readded to mid increasing it. so found is never set to 1 thus returning a negative 1 always.

    so now that i have that established i really have NO clue how to fix this none at all. never done binary search before. i get that they cut the search in half each time through. but outside of that never done one before.

    so what would i have to do to first and last?
    hooch

  10. #10
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    In Stoned_Coder's example, first is 0, last is 1000, and user_id is 20. The first time through the loop, first is 0, last is 1000, and mid is (0 + 1000) / 2 which is 500. Since the value in the array is same as the index in this example, id[500] is just 500, which does not equal 20, so you move into the else block.

    Now id[mid] is id[500] which is 500 in this case, and user_id is 20, so id[mid] < user_id is false because 500 < 20 is false. That puts us in the inner else statement.

    So first = mid + 1 means that first is changing to 500 + 1, or 501. And you will repeat the steps except now you are just looking for 20 in the range 501-1000.

    The point of the binary search is to split the list in two and only look into the half that has the value. You are splitting the list in two, but are you continuing with the half that has the value?

  11. #11
    Registered User
    Join Date
    Nov 2001
    Posts
    255
    yes i see that its going in that range so i need it in range 0-499. so i swap the first and last.

    and yea now it returns a normal number 0

    ok thanks for helping me figure out the madness lol

    and daved i have to ask anytime you post are you always offline cause its like you instantly sign off or have constant ghosting? lol
    hooch

  12. #12
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    It says I'm invisible next to my posts. I probably turned off the show online option when I registered. Or maybe I am just that quick.

  13. #13
    Registered User
    Join Date
    Nov 2001
    Posts
    255
    lol could be but if i catch it saying online ill be sure to printscreen it and sell it on ebay as a rare find lol
    hooch

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Tree scope? problem
    By tms43 in forum C++ Programming
    Replies: 5
    Last Post: 11-01-2006, 10:13 PM
  3. Binary Search tree problem
    By berryski in forum C++ Programming
    Replies: 3
    Last Post: 07-07-2005, 12:47 PM
  4. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 10:18 AM
  5. Problem with binary search tree :(
    By Unregistered in forum C Programming
    Replies: 10
    Last Post: 05-01-2002, 10:31 PM