Nederlandse leereditie

Binair zoeken in een C-array

Zoek een waarde in een gesorteerd array en halveer het bereik bij elke stap.

Lees N, zoekwaarde K en een niet-aflopend gesorteerd array. Geef de vanaf nul getelde index van een voorkomen van K terug, of -1 als K ontbreekt.

Vergelijk de zoekwaarde met het middelste element en verwerp de helft die haar niet kan bevatten. Bij duplicaten mag je elk voorkomen kiezen: het eerste is niet verplicht.

Invoer

N en K, daarna N niet-aflopend gesorteerde gehele getallen.

Uitvoer

Found at index: <index> indien aanwezig, anders Not found: -1.

Voorwaarden

1 ≤ N ≤ 100000; waarden van -10⁹ tot 10⁹.
Zoeken in O(log N) tijd en O(1) extra geheugen.

Hints

Begin met low = 0 en high = N - 1 en ga door zolang low <= high.
Bereken mid = low + (high - low) / 2 en vermijd de directe som van de grenzen.
Gebruik na een ongelijke vergelijking high = mid - 1 of low = mid + 1.

Broncode

#include <stdio.h>

// Function to perform binary search
// Returns 0-based index of target if found, else -1
int binary_search(int arr[], int n, int target) {
    int low = 0;
    int high = n - 1;

    // TODO: Implement O(log N) binary search loop
    // Tip: Use mid = low + (high - low) / 2 to prevent integer overflow

    return -1; // Target not found
}

int main(void) {
    int n, target;
    if (scanf("%d %d", &n, &target) != 2 || n <= 0) {
        return 1;
    }

    int arr[100];
    for (int i = 0; i < n && i < 100; i++) {
        scanf("%d", &arr[i]);
    }

    int result = binary_search(arr, n, target);
    if (result != -1) {
        printf("Found at index: %d\n", result);
    } else {
        printf("Not found: -1\n");
    }

    return 0;
}

Openen in de compiler

Uitleg van de oplossing

Behoud de invariant: als de waarde in het resterende gebied voorkomt, ligt de index tussen low en high inclusief. Gelijkheid beëindigt het zoeken direct.

Als low groter wordt dan high blijven geen kandidaten over: geef -1 terug. Het zoeken is logaritmisch, maar N waarden inlezen kost nog steeds O(N) tijd.

Oplossingscode

#include <stdio.h>

int binary_search(int arr[], int n, int target) {
    int low = 0;
    int high = n - 1;

    while (low <= high) {
        // Overflow-safe midpoint calculation
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

int main(void) {
    int n, target;
    if (scanf("%d %d", &n, &target) != 2 || n <= 0) {
        return 1;
    }

    int arr[100];
    for (int i = 0; i < n && i < 100; i++) {
        scanf("%d", &arr[i]);
    }

    int result = binary_search(arr, n, target);
    if (result != -1) {
        printf("Found at index: %d\n", result);
    } else {
        printf("Not found: -1\n");
    }

    return 0;
}

Veelgestelde vragen

Waarom blijven code en sommige resultaten Engels?

C-sleutelwoorden, namen, programmacommentaar en verwachte uitvoer blijven gelijk aan het origineel om uitvoerbare code en consistente tests te behouden. Uitleg en instructies zijn vertaald.