I'll crack it when I get home, don't you worry. I'll do it whether or not you need it :D
So check back later when I've cracked it open.
Meh, unless someone else does it before me.
Printable View
I'll crack it when I get home, don't you worry. I'll do it whether or not you need it :D
So check back later when I've cracked it open.
Meh, unless someone else does it before me.
Ok Thanks!
I think I have to sleep a little my eyes are slamming shut and I have downed a gallon of coffee! I must be tired!
I haven't tested it, but I suspect you may need to make this:
intoCode:if(first >= last)
return -1;
Otherwise, it will not ever search the first & last positions.Code:if(first > last)
return -1;
I'm only guessing tho'.
--
Mats
I think I may have found it!!!
I removed the '=' from the code:
I haven't checked it completely, but the first few seem to work!Code://Function written for Test 5 Question 22
template<class elemType>
int orderedArrayListType<elemType>::binarySearchImpl(const elemType& item, int first, int last)
{
if(first > last) //REMOVED '=' from this statement and I think that fixed it.
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
template<class elemType>
int orderedArrayListType<elemType>::seqSearch(const elemType& item)
{
for (int loc = 0; loc < length; loc++)
if (list[loc] == item)
return loc;
return -1;
}//end seqSearch on ordered list
We'll see tomorrow. I have to sleep now.
Cindy
From a guessing standpoint, I'm guessing it's a bug, but not THE bug since the elements looked for shouldn't in the last or first index.
Mats you are back! Hey!
That is the second time this evening I have posted something at the same time you all were responding. (no I am not from the south)
I messed around and remembered something similar to that is another program I had to do. And that fixed the problem with that code. I don't know if it fixes everything with this program, but it seems to have helped.
THANKS!!!
But it also applies for middle elements where you end up with a "miss by one" on the next to final search - e.g. mid = 3, but we want element 4, and our previous search had a mid of -> last = 4. Next search will do "first = 4, last = 4" and exit with "not found", rather than check element 4.
Again, it's my sloppy pseudo-code.
[But it's all good debugging experience, even if that's not really what you may feel that you need this very moment, clegs!]
--
Mats
I see.
Well, that's what debuggers are for.
UPDATE:
It seems matsp's suggestion was spot on. Your application works now just fine.
Oh well, it's a shame I hadn't stayed up later. I've just been playing catch up and I noticed the >= instead of > bug, a couple of pages before now.
What it would mean is that half of your items would not be able to be found. If you think of the array as a binary tree, you were only able to find the internal nodes (those that have children), but not the leafs. Once you got to a leaf, you stopped before doing the last compare.
Thanks Elysia, Mats and iMalc for helping figure out my errors and sticking with it. I really appreciate all your help. And Mats, don't worry about it. I have gotten farther with your help regardless of you thinking it is sloppy ... or not. I appreciate all your help. And, the bottom line - it is my code and my errors that brought me here in the first place. So, it took longer and I got more experience in debugging subtle errors. It would have taken me a heck of a lot longer without your help. That is what it is all about - thinking, writing and debugging - the effort of code. I appreciate your time and help. More heads, especially more experienced heads, are better than my one. Thank you!
I too have tested the code and removing the equal sign as noted above is THE fix. I am soooo excited. Three more chapters and 5 more programs along with the final and I can put this class to rest. Next language - Java Script!
Cindy
iMalc, I added your homepage to my C++ resources. It is a shame you didn't stay up later...I finally slept for 1 and 1/2 hours at 4:30am.
Who NEEDS sleep anyway?!
JavaScript.... ugh.
So MacGyver you know Java Script?
This may be a C++ Board, but...
Are you saying that because it is hard, or just bad?
I had Java last semester and it was about to kill me.
JavaScript, huh? I know that too. The one biggest thing I'm possibly most annoyed is the lack of a Sleep function. OH well.
I never took the time to actually formally learn it. I did some really simple stuff with it years ago, but I'm not a fan of many web-based nor most dynamically-typed languages. Sorry. :)
Yea, lately I can relate to a lack of a sleep function. Actually, my sleep function exists, I just don't seem to be able to access it at appropriate times, I think I need a debug routine.
My poor stab at programming humor, or is that an oxymoron?! :D
Elysia, I may just call on you to ask a few questions if the need arises, if you are game. Not here of course! When I was struggling with Java I couldn't find a forum like this one - active, helpful, and always available. I really appreciate the level of sincere helpfulness this forum provides over the others.
MacGyver, I am sorry to hear you aren't versed in JavaScript as well, I appreciate the way you have explained some things.
Ah well, all good things must come to an end.
I really appreciate all the help everyone has afforded me, it has been great.
I am writing like this is the end, but I still have five more programs so I am not gone yet!!! ;)