close

Algoritmu tat-Tiftix Binarju (Binary Search) f'C++- Spjegazzjoni, Eżempju, u Kodiċi

L-algoritmu ta' tfittxija binarja huwa mod aktar effiċjenti ta' tiftix għal element speċifiku f'lista magħżula. B'differenza għat-tfittxija lineari, li tiċċekkja l-elementi b'mod sekwenzjali, it-tfittxija binarja taqsam il-lista f'nofsijiet u tqabbel l-element fil-mira mal-element tan-nofs. Dan il-proċess jiġi ripetut sakemm jinstab l-element fil-mira jew il-firxa tat-tfittxija ssir vojta.

Kif taħdem

  1. Ibda bil-lista kollha magħżula.
  2. Sib l-element tan-nofs tal-firxa tat-tfittxija attwali.
  3. Qabbel l-element tan-nofs mal-valur fil-mira.
  4. Jekk l-element tan-nofs huwa ugwali għall-valur fil-mira, it-tfittxija tirnexxi.
  5. Jekk l-element tan-nofs huwa akbar mill-mira, fittex fin-nofs tax-xellug tal-firxa.
  6. Jekk l-element tan-nofs huwa iżgħar mill-mira, fittex fin-nofs tal-lemin tal-firxa.
  7. Irrepeti l-passi 2-6 sakemm jinstab l-element fil-mira jew il-firxa tat-tfittxija ssir vojta.

Eżempju

Ejja nikkunsidraw lista magħżula ta 'numri interi u trid issib in-numru 34 billi tuża tfittxija binarja.

Lista Magħquda: {12, 23, 34, 45, 56, 67, 89, 90}

  1. Ibda bil-lista kollha.
  2. Element tan-nofs: 56(pożizzjoni 4). Qabbel ma' 34.
  3. 56 huwa akbar minn 34. Fittex fin-nofs tax-xellug.
  4. Element tan-nofs ġdid: 23(pożizzjoni 1). Qabbel ma' 34.
  5. 23 huwa iżgħar minn 34. Fittex fin-nofs tal-lemin.
  6. Element tan-nofs ġdid: 45(pożizzjoni 3). Qabbel ma' 34.
  7. 45 huwa akbar minn 34. Fittex fin-nofs tax-xellug.
  8. Element tan-nofs ġdid: 34(pożizzjoni 2). Mira misjuba.

Eżempju Kodiċi f'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;  
}

Fl-eżempju mogħti, il- binarySearch funzjoni tintuża biex issib in-numru 34 f'lista magħżula ta 'numri interi. Ir-riżultat ikun il-pożizzjoni ta' 34 fil-lista(il-pożizzjonijiet jibdew minn 0) jew -1 jekk in-numru ma jinstabx.