The code for binary search

Here is an iterative implementation (with a loop, no recursion) of binary search. We initialise left to 0 and right to the last index of the array. As long as left is less than or equal to right, there is still a zone to explore.

def recherche_dichotomique(a, cible):
    gauche, droite = 0, len(a) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if a[milieu] == cible:
            return milieu
        elif a[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1

Let us detail the sensitive points. First, the stopping condition gauche <= droite (and not <): if we used <, we would miss the case where the interval contains exactly one element (gauche == droite), which would miss values present in the array.

Next, computing the middle: (gauche + droite) // 2 works fine in Python, but in some languages with limited-size integers, gauche + droite can cause an overflow if the indices are huge; a safer version is gauche + (droite - gauche) // 2, which avoids adding two large numbers.

Finally, updating the bounds must always EXCLUDE the middle already tested: gauche = milieu + 1 and droite = milieu - 1, never gauche = milieu or droite = milieu, otherwise the algorithm may loop forever by re-testing the same index.

check on [1,3,5,7,9,11,13,15], target=7:
step 1 : gauche=0, droite=7, milieu=3, a[3]=7  -> found at index 3

If the target is absent (for example 8 in this array), the loop ends when left passes right, and the function returns -1.