• Post Reply Bookmark Topic Watch Topic
  • New Topic

Failing at binary search  RSS feed

 
khoa tran
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey all,

Ive been working on a program that takes numbers into an array. Then the program uses a boolean binary search to go through the program and returns a true or false value. I seem to have everything right but the program keeps coming back as false. Any help would be appreciated!

Here's my sample output.

Please enter an occupied hotel room number, -1 to quit:
1
2
3
4
5
-1
Please enter a room to search for: 1
This room is "Unoccupied"
1
2
3
4
5
Press any key to continue . . .

here's my program

[redacted]
 
Ivan Jozsef Balazs
Rancher
Posts: 999
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Does it suffice to compare against the middle element? What about the other end of the interval?
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, you initialize your array so that it contains 100 elements. Then you fill it with 5 numbers.
So, your array isn't sorted (the remaining elements are 0).
In your seachBinary, you start by comparing 1 to element 50, which is 0.
So it starts to look in the upper half, and it won't find it there.

In this case, you must also supply to your search routine, the number that indicates
how many elements are filled in your array (in this case 5) and use this number
as the initial upperbound.

 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
khoa tran wrote:I seem to have everything right but the program keeps coming back as false.

Do you see the fallacy in that statement?

Java isn't out to get you, so if it doesn't work then it means you have done something wrong - so when you're debugging, never start out with the notion that "everything [is] right".

My suggestion: add println() statements to your code so you can see the values that the method is working with. That will get you to your solution much quicker. Personally, other than Piet's suggestion, I can see at least one other error in your search method. it is admittedly quite subtle - so subtle in fact that it went undiscovered for 12 years after the algorithm was first published in 1946.

Winston
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
khoa tran wrote:Any help would be appreciated

Just one other thing, and it's very minor, but possibly worth remembering. When you have a "choice" structure (your if...else stuff), it's usually best to eliminate possibilities in the order they're likely to happen - ie, most likely first.

In your case you check
if (searchRoom == midValue)
first, and it's the least likely thing to happen. This means that each iteration of the loop (except possibly the last) will always have to do at least two checks.

Assuming that the check is what you want, you would be better off doing:Like I say, it's not that important, but probably worth remembering, because there may be cases where it does make more of a difference.

Winston
 
khoa tran
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey guys I figured it out, I dropped they array size to 6 and also I read in my textbook that the array needs to be sorted lowest to highest for it to function properly.

I changed int [] occupiedRooms = new int [100];

int [] occupiedRooms = new int [6];

and I added after the array population

for (int i=0; i < occupiedRooms.length; i++
{
Arrays.sort(occupiedRooms);
}

thanks for all the suggestions! =)
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
khoa tran wrote:and I added after the array population

for (int i=0; i < occupiedRooms.length; i++)
{
Arrays.sort(occupiedRooms);
}

That sorts the list 6 times. You only need to sort it once!
 
khoa tran
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
right i guess the for loop is unnecessary
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
khoa tran wrote:Hey guys I figured it out, I dropped they array size to 6 and also I read in my textbook that the array needs to be sorted lowest to highest for it to function properly.

Just FYI - because I'm sure you're simply doing this as an exercise - what you want could be done far more easily (and quickly) with a BitSet.

Winston
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!