Algartam Cuardaigh Dénártha (Binary Search) i C++- Míniú, Sampla, agus Cód

Is bealach níos éifeachtaí é an t-algartam cuardaigh dénártha chun eilimint shonrach a chuardach i liosta sórtáilte. Murab ionann agus cuardach líneach, a sheiceálann eilimintí go seicheamhach, roinneann cuardach dénártha an liosta ina leatha agus cuireann sé an sprioceilim i gcomparáid leis an eilimint mheánach. Déantar an próiseas seo arís agus arís eile go dtí go bhfaightear an sprioceilimint nó go dtiocfaidh an raon cuardaigh folamh.

Conas a oibríonn sé

1. Tosaigh leis an liosta iomlán sórtáilte.
2. Faigh an eilimint lár den raon cuardaigh reatha.
3. Déan comparáid idir an eilimint láir agus an luach sprice.
4. Más ionann an eilimint lár agus an luach sprice, éiríonn leis an gcuardach.
5. Má tá an eilimint lár níos mó ná an sprioc, cuardaigh sa leath clé den raon.
6. Má tá an eilimint lár níos lú ná an sprioc, cuardaigh sa leath ceart den raon.
7. Déan céimeanna 2-6 arís go dtí go bhfaighfear an sprioceilimint nó go dtiocfaidh an raon cuardaigh folamh.

Sampla

Déanaimis machnamh ar liosta sórtáilte slánuimhreacha agus ba mhaith linn an uimhir 34 a fháil ag baint úsáide as cuardach dénártha.

Liosta Sórtáilte: {12, 23, 34, 45, 56, 67, 89, 90}

1. Tosaigh leis an liosta iomlán.
2. Gné lár: 56(seasamh 4). Cuir i gcomparáid le 34.
3. Tá 56 níos mó ná 34. Cuardaigh sa leath clé.
4. Gné lár nua: 23(seasamh 1). Cuir i gcomparáid le 34.
5. Tá 23 níos lú ná 34. Cuardaigh sa leath cheart.
6. Gné lár nua: 45(seasamh 3). Cuir i gcomparáid le 34.
7. Tá 45 níos mó ná 34. Cuardaigh sa leath clé.
8. Gné lár nua: 34(seasamh 2). Sprioc aimsithe.

Cód Samplach i 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;  
}  

Sa sampla tugtha, binarySearch úsáidtear an fheidhm chun an uimhir 34 a fháil i liosta sórtáilte slánuimhreacha. Is é an toradh a bheidh air ná suíomh 34 ar an liosta(tosaíonn na poist ó 0) nó -1 mura bhfaightear an uimhir.