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].Originally Posted by clegs
--
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.
Yes, but matsp was referring to that besides item, you need to pass first and last!
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
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.
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.
I found that TOO!
I will retype and see what I get.
Hang tight!
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)
And here are the functions retyped as discussed: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; }
On the first pass I get number was found but with a -1 returned as the position.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 second pass I get the number wasn't found.
Last edited by clegs; 12-05-2007 at 03:57 AM.
You are searching for x+1 when you print the number. So if you enter 4, is 5 also in the list?Code:intList.binarySearch(x + 1)
--
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.
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.
Do
Instead. Just an optimization.Code:int pos = intList.binarySearch(x) if (pos == -1) // not found else cout << pos; // found
I'll try that!
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.
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!
Matsp made the inital discovery of your subtle bug.
Last edited by Elysia; 12-05-2007 at 04:18 AM.
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.
