Recursion Revisited again, and again!

This is a discussion on Recursion Revisited again, and again! within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by clegs Mats said two parameters passed to binarySearchImpl - first and last, but I actually need three ...

  1. #46
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by clegs View Post
    Mats said two parameters passed to binarySearchImpl - first and last, but I actually need three right, item, first and last!
    Yes, I meant "two parameters for where you're searching", you obviously also need whatever you're searching for - unless you have telepathic code [and my telepathic code usually works very poorly - just like own telepathic abilities].

    --
    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.

  2. #47
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,556
    Yes, but matsp was referring to that besides item, you need to pass first and last!
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #48
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    Ok, I THINK I have written the code as described by mats algorithm, however, I am not finding any numbers in the list (whether they are there for real - not telepathically (that was for you mats) or not!

    I have to be missing something, but ...what? My eyes are blurry and I almost can't see my laptop let alone a missing code statement. or something more subtle than that.

    Sorry, I am getting punchy again!
    Here is the piece of work (it's not art anymore):
    Code:
    template<class elemType> 
    int orderedArrayListType<elemType>::binarySearch(const elemType& item)
    {
    	int first = 0;
    	int last = length - 1;
    	return binarySearchImpl(item, first, last);
    }
    
    //Function written for Test 5 Question 22
    template<class elemType> 
    int orderedArrayListType<elemType>::binarySearchImpl(const elemType& item, int first, int last)
    {
    	
    	if(first >= last)
    		return -1;
    	int mid = (first + last) / 2;
    	if(list[mid] == item)
    		   return mid;
    	if (list[mid] > item)
    		return binarySearchImpl(item, mid + 1, last);
        else
    		return binarySearchImpl(item, first, mid - 1);
    }//end binarySearch

  4. #49
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    That's probably my fault - I got the last/first mixed up in my pseudo-code. If array[mid] > item you should, obviously search between the "first and mid" - so just swap your > with a < in the if-statement deciding which half of the array to search.

    --
    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. #50
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,556
    Code:
    if(list[mid] > item)
    	last = mid - 1;
    else
    	first = mid + 1;
    Code:
    	if (list[mid] > item)
    		return binarySearchImpl(item, mid + 1, last);
        else
    		return binarySearchImpl(item, first, mid - 1);
    So yes, a little mistake, like matsp points out.
    Reverse the if, so it looks like the original algorithm.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #51
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    I found that TOO!
    I will retype and see what I get.
    Hang tight!

  7. #52
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    NOPE! It still says the number isn't found in the list!
    Here is the call to the function in the driver: (I have this same code for two different lists in the driver program)
    Code:
    //using binarySearch function
    	cout << "Enter a number to find in the list: ";
    	int x;
    	cin >> x;
    	if(intList.binarySearch(x) == -1)
    	{
    		cout << "The number " << x << " was not found in: ";
    		intList.print();
    		cout<<endl;
    	}
    	else
    	{
            cout << "The number " << x << " was found in: "; 
    		intList.print();
    		cout << "at position number: " << intList.binarySearch(x + 1) << endl;				
    	}
    And here are the functions retyped as discussed:
    Code:
    template<class elemType> 
    int orderedArrayListType<elemType>::binarySearch(const elemType& item)
    {
    	int first = 0;
    	int last = length - 1;
    	return binarySearchImpl(item, first, last);
    }
    
    //Function written for Test 5 Question 22
    template<class elemType> 
    int orderedArrayListType<elemType>::binarySearchImpl(const elemType& item, int first, int last)
    {
    	
    	if(first >= last)
    		return -1;
    	int mid = (first + last) / 2;
    	if(list[mid] == item)
    		   return mid;
    	if (list[mid] > item)
    		return binarySearchImpl(item, first, mid - 1);
        else
    		return binarySearchImpl(item, mid + 1, last);
    }//end binarySearch
    On the first pass I get number was found but with a -1 returned as the position.
    On the second pass I get the number wasn't found.
    Last edited by clegs; 12-05-2007 at 02:57 AM.

  8. #53
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
    intList.binarySearch(x + 1)
    You are searching for x+1 when you print the number. So if you enter 4, is 5 also in the list?

    --
    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.

  9. #54
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    Yes! The numbers I enter are consecutive and I use the middle values in the list. But, let me put that back to 'x' and see what happens.
    It's a good thing I like coffee.

  10. #55
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,556
    Do
    Code:
    int pos = intList.binarySearch(x)
    if (pos == -1)
    // not found
    else
    cout << pos; // found
    Instead. Just an optimization.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #56
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    I'll try that!

  12. #57
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,556
    It will also avoid your subtle bug since pos is the index in the array it's stored, you won't have to call the binarySearch function a second time to find the position.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  13. #58
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    YAHOOO!!!!! YAHOO!!!!! You did IT!
    That made it all better!
    It works. I can't believe it, I am soooooooo HAPPY!
    If it were earlier I'd be singing in a beer!
    Well, probably not, I'd be working on more CODE!
    But I think that did it, I will try a few more tests, and get back to you!

  14. #59
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,556
    Matsp made the inital discovery of your subtle bug.
    Last edited by Elysia; 12-05-2007 at 03:18 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  15. #60
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    I danced the JIG too fast.
    When I enter a number in the middle of the list on the first pass it finds it. When I look for a number that is the lower or upper limit on the first pass it doesn't find it. And the second call to the function doesn't find any number.

Page 4 of 7 FirstFirst 1234567 LastLast
Popular pages Recent additions subscribe to a feed

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