Algorithm design Ideas?

[warlock07]

So here is the algorithm I am trying to design...i'm not sure it will make any sense.
I have a sequence of n numbers(in ascending order). I have an another number 'x'. If i have 2 chances to compare x with a number greater than it but unlimited chances to compare with numbers lesser than it. Now I have to to find out the maximum possible value in the sequence that is less than x in the most efficient way. I know this looks a little contrived but the original question is different so I am looking for the direction I would need to go.

As an example..watch this..

I have a series from 1,2,3,4...............,19, 20.

Now I have a number x = 10.5

Now I have to find the maximum possible number "M" in the series such that M < x

The easiest way would be brute forcing ur way from the lowest possible number(they are in ascending order anyway.). As soon as the "less than comparison" fails, u have the solution. The worst case would 'n' comparisons. But we have two chances where we can fail the comparison. So a slightly better algorithm would be comparing the odd indexed numbers. So in the worst case scenario we have n/2 +1 comparisons which is better than the first.

Now finally...Is there a better way to approach this problem. Can some one point me in a better direction to solve the algorithm??

[firstPerson]

Just an idea, since the array is ordered. Consider comparing the
mid of the array. If the number X is greater than the mid, then
compare the mid of the top half. Keep this pattern. As soon as you
have failed 2 greater than comparison, then start with the subList thats
being considered and brute force it. That way, the the search
could be in log(n) at worst.

[Ancient Dragon]

google for binary search algorithms.

[edit]Oops! Didn't see firstPerson's response.

[nezachem]

So here is the algorithm I am trying to design...i'm not sure it will make any sense. I have a sequence of n numbers(in ascending order). I have an another number 'x'. If i have 2 chances to compare x with a number greater than it but unlimited chances to compare with numbers lesser than it. Now I have to to find out the maximum possible value in the sequence that is less than x in the most efficient way. I know this looks a little contrived but the original question is different so I am looking for the direction I would need to go.

As an example..watch this..

I have a series from 1,2,3,4...............,19, 20.

Now I have a number x = 10.5

Now I have to find the maximum possible number "M" in the series such that M < x

The easiest way would be brute forcing ur way from the lowest possible number(they are in ascending order anyway.). As soon as the "less than comparison" fails, u have the solution. The worst case would 'n' comparisons. But we have two chances where we can fail the comparison. So a slightly better algorithm would be comparing the odd indexed numbers. So in the worst case scenario we have n/2 +1 comparisons which is better than the first.

So far so good. But you still underuse the second chance. Say, you work your way up with an increment of K. The worst case will give you (N/K) + K comparisons. Which value of K will minimize it?

It is not the best algorithm, but is very close to the best (at least, it gives the right asymptotic behaviour). What's left is (a) to make the increment vary according to the amount of yet untested values, and (b) to prove that it is actually the best.
Good luck.

PS to those who answered before me. The wording of the original problem statement is very confusing. Please reread it carefully. It is a very well-known interview problem, usually formulated as follows:You are given 2 marbles and a skyscraper. Determine a lowest story, such that marble breaks when dropped from it.
A binary search does not work here.

[warlock07]

PS to those who answered before me. The wording of the original problem statement is very confusing. Please reread it carefully. It is a very well-known interview problem, usually formulated as follows: You are given 2 marbles and a skyscraper. Determine a lowest story, such that marble breaks when dropped from it. A binary search does not work here.

LOL found me out...but I rephrased it intentionally so that I wudn't look like I dumped my assignment here.It was my understanding of the problem I found the discussion here too.Will try to understand more and get back. http://forums.xkcd.com/viewtopic.php?f=3&t=199
Thanks to others who responded too

[warlock07]

Just an idea, since the array is ordered. Consider comparing the mid of the array. If the number X is greater than the mid, then compare the mid of the top half. Keep this pattern. As soon as you have failed 2 greater than comparison, then start with the subList thats being considered and brute force it. That way, the the search could be in log(n) at worst.

I've already though of this, but it is it any better than the second case that I've mentioned??

[firstPerson]

So far so good. But you still underuse the second chance. Say, you work your way up with an increment of K. The worst case will give you (N/K) + K comparisons. Which value of K will minimize it?

It is not the best algorithm, but is very close to the best (at least, it gives the right asymptotic behaviour). What's left is (a) to make the increment vary according to the amount of yet untested values, and (b) to prove that it is actually the best. Good luck.

PS to those who answered before me. The wording of the original problem statement is very confusing. Please reread it carefully. It is a very well-known interview problem, usually formulated as follows: You are given 2 marbles and a skyscraper. Determine a lowest story, such that marble breaks when dropped from it. A binary search does not work here.

I wasn't implying full binary search, just a partial binary search.

[nezachem]

I wasn't implying full binary search, just a partial binary search.

The problem with even a partial binary search is that if the very first comparison fails (that is, a first marble breaks at the drop from N/2), you need to test the N/2 storeys with a single marble. This gives the worst case of N/2.

PS: You had a slightly different interpretation of the problem. You allow comparison to continue after 2 failures. This is essentially a 3 marble puzzle - which is interesting by itself.
So, having just 1 marble, the problem takes O(N) drops; with 2 marbles it is O(sqrt(N)). What is the asymptotic for 3 marbles? for k marbles?

[warlock07]

How is it a 3 marble problem?? Its still a 2 marble problem from the way he described it...and I'm scraping the bottom but its been some time that I've done the differential calculus...But given a equation N/K +K, how did u find that at K = sqrt(N ) was the value at which the equation has the minimum value..I've verified the result with experimental data and its true...

[edit]
Sorry...got it now...was derivating the wrong variable
[/edit]

[Johnsmith1]

Hi, You had a slightly different interpretation of the problem.
The problem with even a partial binary search.

[0x69]

I would use such algorithm =>
---------------------------------------------------
index(n) = index(n-1) + K(n) ;
K(n) = K(n-1)*C;
speedUp = (x-numberAt(index(n-2))) / (x-numberAt(index(n-1)));
when speedUp < MaxSpeedUp then C = SpeedUpFactor
when speedUp = MaxSpeedUp then C = 1
when speedUp > MaxSpeedUp then C = 1/SpeedUpFactor
;
MaxSpeedUp = 2;
SpeedUpFactor = 1.5
----------------------------------------------
When you get first failure then do brute-force search from index(n-1).
Definitions:
index(n) - next check index in array (series)
index(n-1) - previous check index
index(n-2) - check index before previous
K(n) - how much indexes we want to advance forward
K(n-1) - last advance value
C - some constant
speedUp - shows how distance to x is changing within 1 move step.
MaxSpeedUp - maximum possible speedUp.
SpeedUpFactor - just some constant again.
-------------------------------------------
I don't know time complexity of this algorithm, but I *feel* that this approach should perform fast enough. The only problem that i see here is how to choose optimally MaxSpeedUp and SpeedUpFactor constants. And it may be that these constants can depend on data distribution profile (linear, exponential, logaritmic, etc.). So it may require to choose optimally these constants. But you get it - main algorithm idea is to vary approach to x from the left by controling *approach speed*. It would be interesting if somebody would measure/say possible O(?) of this algorithm. (Or maybe some day i will check it myself :) )

Good luck !

[nezachem]

I would use such algorithm => --------------------------------------------------- index(n) = index(n-1) + K(n) ; K(n) = K(n-1)*C; speedUp = (x-numberAt(index(n-2))) / (x-numberAt(index(n-1))); when speedUp < MaxSpeedUp then C = SpeedUpFactor when speedUp = MaxSpeedUp then C = 1 when speedUp > MaxSpeedUp then C = 1/SpeedUpFactor ; MaxSpeedUp = 2; SpeedUpFactor = 1.5

An overkill, in my opinion.
Let me show you how I'd do it.
The first thing is to determine the maximal height H(K) (of the skyscraper), which can be resolved in K drops. To do that, we shall observe, that the first drop must be done from exactly K 'th story (is it obvious?). Then, if the marble remains intact, we are left with K-1 tries and H(K)-K stories. Applying the same logic recursively, we end up with

H(k) = K + (K-1) + ... + 1

that is

H(K) = K*(K+1)/2

Solving for K gives the starting point for an H-story building.

[warlock07]

The first thing is to determine the maximal height H(K) (of the skyscraper), which can be resolved in K drops. To do that, we shall observe, that the first drop must be done from exactly K 'th story (is it obvious?). Then, if the marble remains intact, we are left with K-1 tries and H(K)-K stories. Applying the same logic recursively, we end up with Help with Code Tags (Toggle Plain Text)

H(k) = K + (K-1) + ... + 1

H(k) = K + (K-1) + ... + 1 that is Help with Code Tags (Toggle Plain Text)

H(K) = K*(K+1)/2

H(K) = K*(K+1)/2 Solving for K gives the starting point for an H-story building.

How would you say that your algorithm is better like compared to others we've discussed...