Help with an binary search algorithm

100 floor ball algorithm

hello everyone,
please help me with this :

Suppose given two identical crystal balls and n stories building. the goal is to find the least floor so that if you throw the ball from this floor, the ball will break. the rules are:

the two balls break at the same floors.
if a ball breaks at floor i it also breaks at floor i+1.

i have to find the least floor the ball breaks at with minimum number of possible ball throws.

thanks

Re: Help with an algorithm

From what I can gather from what you have said, the fastest way to find the floor where the ball will break is a binary search of all the floors.

So drop the ball from the middle floor n/2 and if it breaks drop it from the floor in the middle of that one and ground n/2 - n/4, or if it doesn't break drop the next one from the floor in between the middle and top floors n/2 + n/4 and keep repeating like this.

I'm not 100% sure this is what you were after though.


Maui

Re: Help with an algorithm

yes, i am looking for something like this. but in some kind of source code with explanation.

thanks

Help with an algorithm

My crystal ball tells me you have homework due Monday and you don't want to spend the weekend writing silly code!

Re: Help with an algorithm

Well I am not going to just write the code for you.

I suggest you google for a 'binary search' example in whichever language you are using.

However I am still not sure this is what was asked.
You did say you had 2 balls, perhaps if you only had 2 balls you might not be able to de a binary search cos you could break them both before you find the apropriate floor.

Perhaps what you have to do (and I don't know the rules of your problem) is start on the 2nd floor and drop a ball, if it doesn't break, drop a ball on the 4th floor etc dropping your 1st ball on every 2nd floor (2n) , untill it broke, then dropping the 2nd ball on that floor -1 (2n -1, where n is the attempt that the first ball broke). So if the second ball breaks you know it was that floor, and if it doesn't you know it was the one above that the 1st ball broke on.

Hope that helps (and makes sence)

Maui