• Post Reply Bookmark Topic Watch Topic
  • New Topic

Binary Search with 3 subsets  RSS feed

 
M Lill
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have created a binary search with 3 subsets, some aslo call it a ternary search and have come up with a minor problem. If you run the code as posted below it just runs until you quit it. If anyother value in the array is searched it is found. I have no clue why its doing this. Hopefully someone can reivew my code and help me out.
 
Stefan Evans
Bartender
Posts: 1837
10
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You are calling a method recursively.

To ensure that your process finishes you have to be able to assert that your search space ALWAYS gets smaller.
i.e if you are calling the search method with start/end you have to ensure that any recursive calls are made on a SMALLER range than the one you are currently looking at.

If you can guarantee that, then you can guarantee your program will always end.

So given that as a hint, can you see any way that this doesn't happen in your current program?

It might also help to put in some debugging code like:



And also some sanity code might help:



That will just cause your code to fail faster and let you debug it faster.
 
Stefan Evans
Bartender
Posts: 1837
10
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Actually, just tried running the code and realised that it wasn't the issue I thought it was. I missed the while loop in your code while I was focusing on the recursion.
However, the logging code that I suggested you put in should allow you to determine what is happening fairly quickly.
You're not covering one of the possible search cases.
Possibly changing your while loop to an if statement will also show up the problem.


i.e.
 
M Lill
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I changed the while to an if and I can see some of whats going on but at this point I am lost on what to do to fix it
 
Stefan Evans
Bartender
Posts: 1837
10
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Changing it from a loop to an if statement, gave me the result of "-1"
That means it is going through all of your if statements for conditions, and falling through to the bottom.

So it is not midpoint1
it is not midpoint2
it is not less than midpoint1
it is not greater than midpoint2

what is left?


 
M Lill
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
so if its not midpoint 1, or 2, and is less than 1 and its not grater than 2 it must fall in between them. thing is I can't figure out how to code that and trust me im working on it
 
M Lill
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Nevermind, took pen and paper to figure it out but I got it now. Thank you for your help and making me think of the answer instead of giving it to me. This is what I came up with and it works
 
Stefan Evans
Bartender
Posts: 1837
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Glad to see you got it going.
Now for an added extra, what happens when you search for something not in the list?

Try

 
M Lill
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stefan Evans wrote:Glad to see you got it going.
Now for an added extra, what happens when you search for something not in the list?

Try



I already fixed that so that I get a return now
 
Campbell Ritchie
Marshal
Posts: 56584
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And welcome to the Ranch
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!