Considérons l’algorithme de recherche dichotomique (binaire) dans un tableau trié :

def binary_search_recursive(arr, x, low=0, high=None):
    if high is None
:
        high = len(arr) - 1
    if
 low > high:
        return -1
    mid = (low + high) // 2
    if
 arr[mid] == x:
        return
 mid
    elif
 arr[mid] < x:
        return binary_search_recursive(arr, x, mid + 1
, high)
    else
:
        return binary_search_recursive(arr, x, low, mid - 1)

Quelle est sa complexité temporelle dans le **pire cas** ?