Get the closest higher value from a sequence

Question

I have a sequence like: 4, 8, 16, 32, 64, 128, 256, 512

now I have a number

a = 5

then

b = 8

means b is the closest higher digit according to a from the sequence.

Now a = x then b = ?

Answer 1

I offer two solutions. The first is probably the most obvious and intuitive. The second is more advanced but more efficient.

Simple and intuitive

---

Here is a simple intuitive approach. The following function returns the closest number greater than or equal to the argument num in the sequence 4, 8, 16, 32, 64, .... The function first assigns n to 4. Then, so long as n is strictly less than the argument num, n is assigned the next value in the sequence and the comparison is made again. Once n is greater than or equal to num, we return n.

def seq_1(num):
     """Returns the closest number greater than or equal to num in the
     sequence 4, 8, 16, 32, 64, ...
     """
     n = 4
     while (n < num):
          n *= 2

     return n

More efficient, but more advanced

---

A less intuitive approach but more efficient is obtained by first recognizing that the sequence is defined by

• a_0 = 4;
• a_n = 2 * a_(n-1) for n in {1, 2, 3, ...}.

Notice how a_(n-1) = 2 * a_(n-2). Substituting this into a_n = 2 * a_(n-1), we obtain a_n = (2 ** 2) * a_(n-2). More generally, through repeated substitutions, we obtain a_n = (2 ** n) * a_(0) or a_n = (2 ** n) * 4 or

a_n = (2 ** (n + 2)) for n in {0, 1, 2, 3, ...}

So the first element a_0 is 2 ** 2 = 4, the second element a_1 is 2 ** 3 = 8, the third is 2 ** 4 = 16 and so on.

This suggests the solution:

def seq_2(num):
     """Returns the closest number greater than or equal to num in the
     sequence 4, 8, 16, 32, 64, ...
     """
     if num < 4:
          return 4
     return 1 << (num - 1).bit_length()

• if num is less than 4 we return 4.
• 1 << (num - 1).bit_length() evaluates to the closest power of 2 greater than or equal to num.

This requires the following knowledge:

• 2 is 10 in binary, 2 ** 2 is 100 in binary, 2 ** 3 is 1000 in binary, ..., 2 ** n in binary is 1 followed by n zeros.
• bit_length() is a method defined for Python ints that "[r]eturn[s] the number of bits necessary to represent an integer in binary" (docs).
• i << j shifts i left by j bits. For example

In [1]: bin(1)
Out[1]: '0b1'          # 2 to the power of 0.

In [2]: bin(1 << 5)
Out[2]: '0b100000'     # 2 to the power of 5.

Timings

---

# seq_1(420_000)
657 ns ± 0.55 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
# seq_2(420_000)
116 ns ± 0.416 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

Answer 2

Providing that your sequence is in ascending sorted order then:

seq = [4,8,16,32,64,128,256,512]

def get_next_highest(seq, a):
    b = None
    for i in range(len(seq)-1, -1, -1):
        if seq[i] <= a:
            break
        b = seq[i]
    return b


print(get_next_highest(seq, 5))

Answer 3

If you have a sorted sequence you can use bisect from Pythons standard library.

import bisect

data = [4, 8, 16, 32, 64, 128, 256, 512]
a = 5
index = bisect.bisect(data, a)
b = data[index]

You will have to add a boundary check if you expect a to have a value larger than the last element of the list.

---

This code demonstrates how it works with random values.

import bisect
import random


def get_next_highest(data, value):
    try:
        return data[bisect.bisect(data, value)]
    except IndexError:
        return None


def main():
    data = sorted([random.randint(1, 100) for _ in range(10)])
    a = 50
    b = get_next_highest(data, a)
    print(data, a, b)


if __name__ == '__main__':
    main()