Author |
Topic: Binary search for a fraction (Read 3439 times) |
|
Skandh
Junior Member
Gender: 
Posts: 77
|
 |
Binary search for a fraction
« on: Sep 12th, 2011, 12:24pm » |
 Quote  Modify
|
Trying to solve problem from Roert Sedgewick ( http://algs4.cs.princeton.edu/14analysis/ : Problem 23) .
Binary search for a fraction. Devise a method that uses a logarithmic number of queries of the form Is the number less than x? to find a rational number p / q such that 0 < p < q < N.
Hint: Two fractions with denominator less than N cannot differ by more than than 1/N^2.
But I am not able to completely understand the problem and hint (I doubt hint is incorrect).
At first place, what is significance of query 'Is the number less than x?'
For hint : If N = 5 then 1/2 and 1/3 (2 < 5 , 3 < 5 ).
1/2 - 1/3 = 1/6 > 1/5^2
Please help to understand this problem.
Thanks
|
|
 IP Logged |
I wanna pull by legs!!!
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Binary search for a fraction
« Reply #1 on: Sep 12th, 2011, 12:55pm » |
Quote Modify
|
From what I could make out -
Input to your algo = p, q
Output of your algo = true if p/q found
Your algo template,
BinarySearchFraction(p, q, x) {
if (x == p/q) return true;
else if (p/q < x) {
x = new_guess_for_x;
} else {
x = new_guess_for_x;
}
BinarySearchFraction(p, q, x);
}
Restriction is that your algo should make only log(N) comparisons (i.e p/q < x should be evaluated only log N times).
As you say, the hint definitely seems at odds with itself. Assuming, (a/b) > (c/d), then (a/b) - (c/d) = (ad - bc)/bd >= (ad - bc)/N^2 >= 1/N^2. Maybe they meant to say that the difference is always greater than 1/N^2.
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Skandh
Junior Member
Gender:
Posts: 77
|
|
Re: Binary search for a fraction
« Reply #2 on: Sep 13th, 2011, 8:00am » |
Quote Modify
|
Thanks TenaliRaman for reply.
But doesn't providing p and q and searching whether p/q exists makes the problem trivial? We have p and q so p/q will definitely exist. (Can't say what's the use of finding them ).
Looks like author has left this question for solver's imagination and interpretation. 
But Hint might suggest something, as you have pointed out the difference is always greater than 1/N^2, so does it asking us to divide (0,1] in N^2 interval and find p/q, but that again makes problem trivial (we have answer ready in constant time = 1/2).
|
|
IP Logged |
I wanna pull by legs!!!
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Binary search for a fraction
« Reply #3 on: Sep 14th, 2011, 12:49am » |
Quote Modify
|
The question isn't clear. If the question is: "find a rational number p / q such that 0 < p < q < N.", then p/q = 1/2 is a solution for any N>2.
There must be some condition, for example you want to have p/q=x, but you don't know x, you can only ask if your guess p'/q' is less than x.
The hint should help you to decide when to stop searching. You cannot ask whether your p/q equals the target x.
Anyway, I'd probably walk down the Stern-Brocot tree.
|
| « Last Edit: Sep 14th, 2011, 12:54am by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print