On dirait que ça marche avec les tests

search_binary_recurs.py

def binary_search(seq, x):
    def recurs(low, high):
        if low <= high:
            mid = low + (high - low) / 2
            if x < seq[mid]:
                return recurs(low, mid-1)
            elif x > seq[mid]:
                return recurs(mid+1, high)
            else:
                return mid
    return recurs(0, len(seq) - 1)

Super, comme d'habitude 😃

S'il faut trouver quelque chose à redire:

• Je ne comprends pas trop quelle est ton intention en plaçant les initialisations de low et high avant la définition de la fonction récursive interne.
• Tu n'as pas besoin de passer seq et x à recurs, leur valeur est constante à l'intérieur de la fonction binary_search.

(De mon côté, ça me fait prendre conscience que je dois uniformiser mes notations par rapport à la version impérative qu'on avait faite il y a quelques semaines.)

Dans mon cours de programmation fonctionnelle en DUT 2, je fais implanter cet algorithme en Ocaml, et ça donne ça:

let dicho x v =
    let rec urs a b =
        if a > b then
             None
        else
            let m = (a + b) / 2 in
                if v.(m) = x then
                    Some m
                else
                    if v.(m) > x then
                        urs a (m-1)
                    else
                        urs (m+1) b
    in urs 0 (Array.length v - 1)
;;

Ou, plus brièvement, avec une fonction compare qui renvoie 0, 1 ou -1:

let dicho x v =
    let rec urs a b =
        if a > b then
             None
        else
            let m = (a + b) / 2 in
                match compare v.(m) x with
                | 0 -> Some m
                | 1 -> urs a (m-1)
                | _ -> urs (m+1) b
    in urs 0 (Array.length v - 1)
;;

Comme tu vois, les différences d'implantation entre Ocaml et Python sont ici purement syntaxiques. On est vraiment dans un style fonctionnel.

Eh bien merci beaucoup
Et je ne comprends pas grand chose à Ocaml... j'ai un ami en prépa qui m'a montré très rapidement et je comprends vraiment que les trucs de base....

Ok pour la révision, selon moi c'est parfait.

Les deux programmes sont très similaires, ça devrait t'aider à comprendre.

• La construction let x = e1 in e2 se lit: « valeur de l'expression e2, mais avec tous les x remplacés par l'expression e1 ».
• Il n'y a pas de return car tout est expression. Par exemple, le if c then e1 else e2 est une expression (exactement équivalente à c?e1:e2 en C ou e1 if c else e2 en Python.
• Une expression a un et un seul type: par exemple, dans if c then e1 else e2, les e1 et e2 ne peuvent pas être de type différent. Ça pose un problème pour cette fonction qui doit renvoyer soit un entier (indice), soit rien du tout si l'élément n'existe pas. On contourne le problème en étendant le type entier d'une valeur supplémentaire qui signifie: « absence de valeur ». C'est un type option. Ici, un entier « optionnel » est soit un certain entier x (Some x), soit rien du tout (None).

Mais je suis d'accord que le paradigme fonctionnel est difficile à comprendre à partir du moment où l'on a été « formaté » avec de l'impératif. C'était mon cas, et j'ai dû oublier et réapprendre OCaml plusieurs fois avant de l'intégrer complètement.