close

Binair (Binary Search) zoekalgoritme in C++- uitleg, voorbeeld en code

Het binaire zoekalgoritme is een efficiëntere manier om naar een specifiek element in een gesorteerde lijst te zoeken. In tegenstelling tot lineair zoeken, waarbij elementen opeenvolgend worden gecontroleerd, verdeelt binair zoeken de lijst in twee helften en vergelijkt het doelelement met het middelste element. Dit proces wordt herhaald totdat het doelelement is gevonden of het zoekbereik leeg is.

Hoe het werkt

  1. Begin met de hele gesorteerde lijst.
  2. Zoek het middelste element van het huidige zoekbereik.
  3. Vergelijk het middelste element met de doelwaarde.
  4. Als het middelste element gelijk is aan de doelwaarde, is de zoekopdracht geslaagd.
  5. Als het middelste element groter is dan het doel, zoek dan in de linkerhelft van het bereik.
  6. Als het middelste element kleiner is dan het doel, zoek dan in de rechterhelft van het bereik.
  7. Herhaal stappen 2-6 totdat het doelelement is gevonden of het zoekbereik leeg is.

Voorbeeld

Laten we een gesorteerde lijst met gehele getallen bekijken en het getal 34 willen vinden met behulp van binair zoeken.

Gesorteerde lijst: {12, 23, 34, 45, 56, 67, 89, 90}

  1. Begin met de hele lijst.
  2. Middelste element: 56(positie 4). Vergelijk met 34.
  3. 56 is groter dan 34. Zoek in de linkerhelft.
  4. Nieuw middenelement: 23(positie 1). Vergelijk met 34.
  5. 23 is kleiner dan 34. Zoek in de rechterhelft.
  6. Nieuw middenelement: 45(positie 3). Vergelijk met 34.
  7. 45 is groter dan 34. Zoek in de linkerhelft.
  8. Nieuw middenelement: 34(positie 2). Doel gevonden.

Voorbeeldcode in C++ 

#include <iostream>  
#include <vector>  
  
int binarySearch(const std::vector<int>& arr, int target) {  
    int left = 0;  
    int right = arr.size()- 1;  
  
    while(left <= right) {  
        int mid = left +(right- left) / 2;  
  
        if(arr[mid] == target) {  
            return mid;  
        } else if(arr[mid] < target) {  
            left = mid + 1;  
        } else {  
            right = mid- 1;  
        }  
    }  
  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 23, 34, 45, 56, 67, 89, 90};  
    int target = 34;  
  
    int result = binarySearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}

In het gegeven voorbeeld binarySearch wordt de functie gebruikt om het getal 34 te vinden in een gesorteerde lijst met gehele getallen. Het resultaat is de positie van 34 in de lijst(posities beginnen vanaf 0) of -1 als het nummer niet wordt gevonden.