La fonction blog

Pour parler du nombre d'opérations de l'algorithme de dichotomie, on rappelle ici la définition de la fonction blog, qui a été définie dans le chapitre sur l'écriture des entiers positifs.

Définition de la fonction blog

Définition

Tout entier naturel $n$ (non nul) est compris entre deux puissances de 2: $2^k \leqslant n < 2^{k+1}$.

Le nombre $k$ sera appelé blog(n).

Remarque: blog(n) est donc le plus grand des entiers i vérifiant 2ⁱ ≤ n.

Lien avec l'écriture binaire d'un entier

Propriété

Le nombre de chiffres dans l'écriture en base 2 d'un entier naturel $n$ (non nul) est égal à blog(n)+1.

Calcul de blog(n) par une fonction python

def blog(n):
    """
    n -- entier naturel non nul
    renvoie blog(n)
    """
    k = 0
    p = 1 # contiendra les puissances de 2 successives
    while p <= n:
        k += 1
        p *= 2
    return k-1

Exercice

Donner les valeurs de blog(1), blog(2), blog(3), blog(4).

Solution

• $2^0 \leqslant 1 < 2^1$: blog(1) = 0.
• $2^1 \leqslant 2 < 2^2$: blog(2) = 1.
• $2^1 \leqslant 3 < 2^2$: blog(3) = 1.
• $2^2 \leqslant 4 < 2^3$: blog(1) = 2.