Java Programmers, lend me your thoughts.

[thehoodedsmack]

So here's the program I'm working on. It's just a simple exercise to test the new stuff we've learned in class. That being recurssion. I keep getting a java.lang.StackOverflowError, so if anyone sees an obvious flaw in my method, please tell me, and I'll be sure to fix it right away. Thanks in advance.



public static void PhoneBookSearch(String someString, int startPage, int endPage)
{
....String[] phoneBookData = new String [26];

....phoneBookData[0] = "accountants";
....phoneBookData[1] = "boats";
....phoneBookData[2] = "contractors";
....phoneBookData[3] = "dog breeders";
....phoneBookData[4] = "entertainers";
....phoneBookData[5] = "farm supplies";
....phoneBookData[6] = "goldsmiths";
....phoneBookData[7] = "hard hats";
....phoneBookData[8] = "ipods";
....phoneBookData[9] = "jazz music";
....phoneBookData[10] = "keys";
....phoneBookData[11] = "land mines";
....phoneBookData[12] = "mortar shells";
....phoneBookData[13] = "nuclear weapons";
....phoneBookData[14] = "oranges";
....phoneBookData[15] = "public services";
....phoneBookData[16] = "quail trainers";
....phoneBookData[17] = "remote controls";
....phoneBookData[18] = "skis";
....phoneBookData[19] = "tree removal";
....phoneBookData[20] = "u-haul";
....phoneBookData[21] = "virus removal software";
....phoneBookData[22] = "waste management";
....phoneBookData[23] = "xylophones";
....phoneBookData[24] = "yard supplies";
....phoneBookData[25] = "zoos";

....if (startPage == endPage)
....{
........if (someString == phoneBookData[startPage])
........{
............System.out.println("Found it! " + someString + " was on page " + startPage + ".");
........}
........else
........{
............System.out.println("Item not in the book");
........}
....}

....else
....{
........int midPage = (endPage-startPage)/2;

........if (someString == phoneBookData[midPage])
........{
............System.out.println("Found it! " + someString + " was on page " + midPage + ".");
........}
........else
........{
............if ((someString).compareTo(phoneBookData[midPage])<0)
............{
................PhoneBookSearch(someString,startPa ge,midPage);
............}
............else
............{
................PhoneBookSearch(someString,midPage ,endPage);
............}
........}
....}
}

public static void main (String[] args)
{
....PhoneBookSearch("nuclear weapons", 0, 25);
}

[Rob Oplawar]

Yes. think of what happens when you do a search on, say, PhoneBookSearch("blarg", 0, 1):
midpage will be (1-0)/2 = 1, and it will recursively call PhoneBookSearch("blarg", 0, 1) again.

Isn't infinite recursion fun?
You need to better define your base case, and make sure that it will always decompose to that case eventually.

e: also, shouldn't this be in the tech talk thread?

[Chewy Gumball]

Pretty sure midpage would be 0 in that case, as the int just cuts off the decimals, but it wouldnt be the stack overflow error. I see you problem though, it is your

int midPage = (endPage-startPage)/2;

I think you want it to be int midPage = startPage+((endPage-startPage)/2);

Doing a trace is will always find your problem if your code is to blame.

If you send in 0 and 25 first, it will skip to the else, make midpage 12 then go down and send in 12 and 25 in again
this will skip again to the else where it will set midpage to 6 (25-12= 13 13/2=6.5 but 6.5 inted is just 6) and then send in 6 and 25

this will then skip to the else and make midpoint (25-6)/2 = 9 (9.5 inted)

9,25 midpoint = 7
7,25 midpoint = 9

and then it goes into an infinite loop.

[thehoodedsmack]

Thanks guys. I'll be sure to test your ideas in class tomorrow.

[Rob Oplawar]

ah, thank you gumball, I had a feeling I was wrong with that. I didn't know if Java automatically floor()s or ciel()s or round()s integers- I was assuming round().
Good catch with the startPage+ bit.

[TheGhost]

Oh, a binary search I see.