Teaching Kids Programming – Binary Search Algorithm to Compute the Logarithm Base Two Function

Teaching Kids Programming: Videos on Data Structures and Algorithms

Since is monotonously increasing, we can use the Binary Search Algorithm (Binary Search Algorithm to Find the Inverse of a Monotone Increasing Function) to compute the Logarithm Base Two Function i.e. .

The input x is given strictly larger than zero, so we can initialize the left boundary to zero, and upperbound to x when given x is larger than 1. However, when it is below 1 and larger than 0, the lowerbound is negative infinity and upperbound is zero, we can use the following equation to turn it into the case when x is larger than 1.

def log2(x):
    if x <= 0:
        return None
    if x < 1:
        return -log2(1.0/x)
    left, right = 0, x
    mid = (left + right) / 2
    cur = pow(2, mid)
    while abs(cur - x) >= 1e-8:
        mid = (left + right) * 0.5
        cur = pow(2, mid)
        if cur >= x:
            right = mid
        else:
            left = mid
    return mid

print(log2(0.1)) # -3.321928095538169
print(log2(1)) # 7.450580596923828e-09
print(log2(2)) # 1.0
print(log2(1024)) # 10.0
print(log2(8)) # 3.0
print(log2(234)) # 7.870364719601639

–EOF (The Ultimate Computing & Technology Blog)