Nederlandse leereditie

Voorbeeld van binair zoeken in C

Vind een element in een gesorteerd array door het zoekgebied te halveren.

Binair zoeken vereist een gesorteerd array. Vergelijk de zoekwaarde met het middelste element: verwerp rechts bij een kleinere waarde en links bij een grotere. Gelijkheid levert de gezochte index op.

Bereken het midden met low + (high - low) / 2 om optellen van grote indices te vermijden. Sluit het geteste midden uit bij het aanpassen van grenzen. Als low groter wordt dan high, ontbreekt de waarde.

De iteratieve versie kost O(log N) tijd en O(1) hulpruimte. Test uiteinden, ontbrekende waarden en één element. Bij duplicaten is de teruggegeven index niet noodzakelijk het eerste voorkomen.

Broncode

#include <stdio.h>

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

    while (low <= high) {
        // Prevent (low + high) integer overflow
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) return mid;
        if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1; // Target not found
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 23;
    int result = binarySearch(arr, n, target);

    if (result != -1)
        printf("Element %d found at index %d\n", target, result);
    else
        printf("Element %d not present\n", target);

    return 0;
}

Openen in de compiler

Verwacht resultaat

Element 23 found at index 5

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.