mp2i-info/td2/td2.md

TD2

Algorythme dichotomique en C

int f(int t[], int target, int len) {
    int min = 0;
    int max = len-1;
    while (min < max) {
        int i = (min+max)/2
        int val = t[i];
        if (target < val) {
            max = i;
        } else if (target > val) {
            min = i;
        } else {
            min = i;
            max = i;
        }
    }
    return min;
}

Preuve de terminaison :

• variant : \lfloor log_2(\frac{max-min}{2}) \rfloor

Preuve de correction :

• invariant : min \leq i_{target} \leq max

• après la boucle : min = max

  donc min \leq i_{target} \leq min

  donc i_{target} = min

Complexité : O(log_2(n))