Binary search for a fraction

Question

I'm trying to solve an exercise from the book Algorithms from Sedgewick that goes as follows:

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 denominators less than N cannot differ by more than 1/N^2.

I'm aware that the interval in which I have to Binary Search is ]0, 1[ but I'm not sure of what I should be looking and what N is. Can somebody please explain it to me?

Answer 1

Ignoring the hint, here is a solution to a much harder problem.

Namely find any rational by binary search, with a logarithmic bound on the absolute value of the numerator/denominator, without knowing in advance how big that is.

It is a binary search of the Stern-Brocot tree.

class GuessState:
    def __init__ (self):
        self.direction = None
        self.start = [0, 1]
        self.bound = [0, 0]
        self.multiple_upper = 1
        self.multiple_lower = 1
        self.is_widening = True
        self.is_choosing = None

    def next_guess (self):
        if self.is_widening:
            multiple = self.multiple_upper
        else:
            multiple = (self.multiple_lower + self.multiple_upper) // 2
        return (self.start[0] + multiple * self.bound[0], self.start[1] + multiple * self.bound[1])

    def add_response (self, response):
        next_level = False
        if self.direction is None:
            if 0 < response:
                self.bound[0] = 1
                self.direction = 1
            else:
                self.bound[0] = -1
                self.direction = -1
            self.is_choosing = True
            return
        elif self.is_choosing:
            if self.direction * response < 0:
                # Reverse direction.
                self.direction = - self.direction
                (self.start, self.bound) = (self.bound, self.start)
            self.multiple_upper = 2
            self.is_choosing = False
        elif self.is_widening:
            if 0 < response * self.direction:
                self.multiple_lower = self.multiple_upper
                self.multiple_upper += self.multiple_upper
            else:
                self.is_widening = False
                if self.multiple_lower + 1 == self.multiple_upper:
                    next_level = True
        elif self.multiple_lower + 1 < self.multiple_upper:
            if 0 < self.direction * response:
                self.multiple_lower = (self.multiple_lower + self.multiple_upper) // 2
            else:
                self.multiple_upper = (self.multiple_lower + self.multiple_upper) // 2
        else:
            next_level = True

        if next_level:
            next_start = (self.start[0] + self.multiple_lower * self.bound[0], self.start[1] + self.multiple_lower * self.bound[1])
            next_bound = (self.start[0] + self.multiple_upper * self.bound[0], self.start[1] + self.multiple_upper * self.bound[1])
            self.start = next_start
            self.bound = next_bound
            self.multiple_lower = 1
            self.multiple_upper = 1
            self.is_choosing = True
            self.is_widening = True

def guesser (answerer):
    state = GuessState()
    response = answerer(state.next_guess())
    while response != 0:
        state.add_response(response)
        response = answerer(state.next_guess())
    return state.next_guess()

def answerer (answer):
    def compare (guess):
        val = guess[0] / guess[1]
        print(f"Comparing answer {answer} to guess {val} ({guess[0]}/{guess[1]})")
        if val < answer:
            return 1
        elif answer < val:
            return -1
        else:
            return 0
    return compare

print(guesser(answerer(0.124356)))

Answer 2

What you are asked here is to find the closest Farey number of order n = N-1 to a given rational x, where x is within [0,1], and x and N are input parameters. You could possibly just do a brute-force search of the closest number to x as in the following snippet:

public static void BruteForce(double x, int N, out int numerator, out int denominator)
{
    // Farey sequence of order n = N-1: 
    int n = N - 1;

    // Find the closest Farey number [0/1,1/n,...(n-1)/n,1/1] to the 'x' given... 
    double min_diff = 1.0;
    int num_closest = 0;
    int denom_closest = 0;
    for (int denom = 1; denom < n + 1; denom++)
    {
        for (int num = 1; num < denom; num++)
        {
            double r = (double)num / (double)denom;
            double diff = System.Math.Abs(x - r);
            if (diff < min_diff)
            {
                min_diff = diff;
                num_closest = num;
                denom_closest = denom;
            }
        }
    }

    numerator = num_closest;
    denominator = denom_closest;
}

This algorithm though has the quadratic order of growth and not so useful.

The better approach is to exploit the properties of Farey pairs. As the Farey mediant property theorem states if p=a/b and q=c/d>p are fractions in lowest terms and there's no fraction between them with smaller denominator than either, the fraction ? with the smallest denominator is (a+c)/(b+d). This fraction is called "mediant" and it splits the Farey sequence into two intervals [0/1,...,?] and [?,...,1/1] with neither has numbers with denominators lower than the mediant itself. The above theorem can now be applied to the interval containing the rational parameter x. If the mediant found has the denominator higher than the order n of the Farey sequence, it means that the search is over and the search interval now contains only two Farey rationals and we need to pick the one closest to x. The algorithm is as follows (thanks to Yakov Galka) with some subtle tweaks:

public static void MediantSearch(double x, int N, out int numerator, out int denominator)
{
    // Farey sequence of order n = N-1: 
    int order = N - 1;

    // Numerator and denominator bounds... 
    int n = order - 1;
    int d = order;

    // Define the search bounds... 
    int lo_num = 0; int lo_denom = 1;
    int hi_num = 1; int hi_denom = 1;

    while(true)
    {
        int mediant_num = lo_num + hi_num;
        int mediant_denom = lo_denom + hi_denom;

        if(mediant_denom > d)
        {
            // Break the search and return the closest... 
            if((x - (double)lo_num/(double)lo_denom) < ((double)hi_num/(double)hi_denom - x))
            {
                numerator = lo_num;
                denominator = lo_denom;
            }
            else
            {
                numerator = hi_num;
                denominator = hi_denom;
            }

            break;
        }

        if((double)mediant_num/(double)mediant_denom < x)
        {
            lo_num = mediant_num;
            lo_denom = mediant_denom;
        }
        else if((double)mediant_num / (double)mediant_denom > x)
        {
            hi_num = mediant_num;
            hi_denom = mediant_denom;
        }
        else
        {
            numerator = mediant_num;
            denominator = mediant_denom;
            break;
        }
    }
}

The algorithm has logarithmic order of growth O(log(n)).