Recursion Revisited again, and again!

**Elysia** · 12-05-2007

I'll crack it when I get home, don't you worry. I'll do it whether or not you need it

So check back later when I've cracked it open.
Meh, unless someone else does it before me.

**clegs** · 12-05-2007

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!

**matsp** · 12-05-2007

I haven't tested it, but I suspect you may need to make this:

Code:

	if(first >= last)
		return -1;

into

Code:

	if(first > last)
		return -1;

Otherwise, it will not ever search the first & last positions.

I'm only guessing tho'.

--
Mats

**clegs** · 12-05-2007

I think I may have found it!!!
I removed the '=' from the code:

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

I haven't checked it completely, but the first few seem to work!
We'll see tomorrow. I have to sleep now.
Cindy

**Elysia** · 12-05-2007

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.

**clegs** · 12-05-2007

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

**matsp** · 12-05-2007

Originally Posted by Elysia

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.

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

**Elysia** · 12-05-2007

I see.
Well, that's what debuggers are for.

UPDATE:
It seems matsp's suggestion was spot on. Your application works now just fine.

**iMalc** · 12-05-2007

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.

**clegs** · 12-05-2007

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?!

**MacGyver** · 12-05-2007

JavaScript.... ugh.

**clegs** · 12-05-2007

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.

**Elysia** · 12-06-2007

JavaScript, huh? I know that too. The one biggest thing I'm possibly most annoyed is the lack of a Sleep function. OH well.

**MacGyver** · 12-06-2007

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.

**clegs** · 12-06-2007

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?!

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

Thread: Recursion Revisited again, and again!

Thread Tools

Search Thread

Display