Metody Programowania - Lista 6

Zadanie 1

Zakładamy że obowiązują deklaracje:

    int a[N];
    int i, j, k, x;

Zakładamy również że elementy tablcy `a' są uporządkowane rosnąco. Procedura wyszukiwania binarnego ma się zatrzymać z `a[k]==x' jeśli takie `k' istnieje i z `a[k]!=x' w przeciwnym przypadku. Które z poniższych fragmentów są poprawne, jak można poprawić pozostałe, które są bardziej wydajne?

Fragment A:

    i = 0; 
    j = N-1;
    do {
        k = (i+j)/2;
        if (a[k]<x) {
            i = k; 
        } else {
            j = k;
        }
    } while (a[k]!=x && i<j);

Fragment B:

    i = 0; 
    j = N-1;
    do {
        k = (i+j)/2;
        if (x<a[k]) {
            j = k;
        } else {
            i = k+1;
        }
    } while (i<j);

Fragment C:

    i = 0;
    j = N-1;
    do {
        k = (i+j)/2;
        if (x<=a[k]) {
            j = k-1;
        }
        if (a[k]<=x) {
            i = k+1;
        }
    } while (i<=j);

Fragment D:

    i = 0;
    j = N-1;
    k = (i+j)/2;
    while(<j) {
        if (a[k]==x) {
            break;
        }
        if (a[k]<x) {
            i = k+1;
        } else {
            j = k-1;
        }
    }

Zadanie 2