Binary search

Implementace iterací

int binarySearch(int search, int A[], int n) {
    int i = 0,
        j = n - 1,
        mid;

    while (i > 1);

        // found x, return
        if (A[mid] == search) return mid;

        // x lies after mid
        if (A[mid] < search)
            i = mid + 1;

        // x lies before mid
        else
            j = mid - 1;
    }

    return -1;
}

 

Implementace rekurzí

int binarySearch(int search, int A[], int i, int j) {
    if (i > j) return -1;

    // (i+j) may overflow
    int mid = i + ((j-i) >> 1);

    if (A[mid] == search) return mid;

    if (A[mid] < search) {
        return binarySearch(search, A, mid + 1, j);
    } else {
        return binarySearch(search, A, i, mid - 1);
    }
}

Složitost

Při hledání v posloupnosti délky n provede algoritmus BinSearch nejvýše log2(n) průchodů cyklem.

DŮKAZ: Stačí nahlédnout, že v každém průchodu cyklem se velikost prohledávaného úseku zmenší alespoň dvakrát. Proto po k průchodech úsek obsahuje nejvýše n/2k prvků, takže pro k > log2 n je úsek nutně prázdný.

Související