Binary selection process

Question

I have been working on what seems to be a simple task that is driving me nuts. So if you fancy a programming challenge ... read on.

I want to be able to take a number range e.g. [1:20] and print the values using a mechanism similar to a binary serach algorithm. So, print first the lowest value (in this case 1) and then the mid value (e.g. in this case 10) and then divide the range into quarters and print the values at 1/4 and 3/4 (in this case, 5 and 15) and then divide into eights and so on until all values in the range have been printed.

The application of this (which isn't really necessary to understand here) is for a memory page access mechanism that behaves more efficiently when pages are accessed at the mid ranges first.

For this problem, it would be sufficient to take any number range and print the values in the manner described above.

Any thoughts on this? A psuedo code solution would be fine. I would show an attempt to this but everything I've tried so far doesn't cut it. Thanks.

Update: As requested, the desired output for the example [1:20] would be something like this: 1, 10, 5, 15, 3, 7, 12, 17, 2, 4, 6, 8, 11, 13, 16, 18, 9, 19, 20

This output could be presented in many similar ways depending on the algorithm used. But, the idea is to display first the half values, then the quarters, then the eights, then 16ths, etc leaving out previously presented values.

Answer 1

Here is some Python code producing similar output to your example:

def f(low, high):
    ranges = collections.deque([(low, high)])
    while ranges:
        low, high = ranges.popleft()
        mid = (low + high) // 2
        yield mid
        if low < mid:
            ranges.append((low, mid))
        if mid + 1 < high:
            ranges.append((mid + 1, high))

Example:

>>> list(f(0, 20))
[10, 5, 15, 2, 8, 13, 18, 1, 4, 7, 9, 12, 14, 17, 19, 0, 3, 6, 11, 16]

The low, high range excludes the endpoint, as is convention in Python, so the result contains the numbers from 0 to 19.

The code uses a FIFO to store the subranges that still need to be processed. The FIFO is initialised with the full range. In each iteration, the next range is popped and the mid-point yielded. Then, the lower and upper subrange of the current range is appended to the FIFO if they are non-empty.

Edit: Here is a completely different implementation in C99:

#include <stdio.h>

int main()
{
    const unsigned n = 20;
    for (unsigned i = 1; n >> (i - 1); ++i) {
        unsigned last = n;    // guaranteed to be different from all x values
        unsigned count = 1;
        for (unsigned j = 1; j < (1 << i); ++j) {
            const unsigned x = (n * j) >> i;
            if (last == x) {
                ++count;
            } else {
                if (count == 1 && !(j & 1)) {
                    printf("%u\n", last);
                }
                count = 1;
                last = x;
            }
        }
        if (count == 1)
            printf("%u\n", last);
    }
    return 0;
}

This avoids the necessity of a FIFO by using some tricks to determine if an integer has already occured in an earlier iteration.

You could also easily implement the original solution in C. Since you know the maximum size of the FIFO (I guess it's something like (n+1)/2, but you would need to double check this), you can use a ring buffer to hold the queued ranges.

Edit 2: Here is yet another solution in C99. It is optimised to do only half the loop iterations and to use only bit oprations and additions, no multiplication or divisions. It's also more succinct, and it does not include 0 in the results, so you can have this go at the beginning as you initially intended.

for (int i = 1; n >> (i - 1); ++i) {
    const int m = 1 << i;
    for (int x = n; x < (n << i); x += n << 1) {
        const int k = x & (m - 1);
        if (m - n <= k && k < n)
            printf("%u\n", x >> i);
    }
}

(This is the code I intended to write right from the beginning, but it took me some time to wrap my head around it.)