(Binary Search) C++'da İkili Arama Algoritması- Açıklama, Örnek ve Kod

İkili arama algoritması, sıralanmış bir listede belirli bir öğeyi aramanın daha etkili bir yoludur. Öğeleri sırayla kontrol eden doğrusal aramanın aksine, ikili arama listeyi ikiye böler ve hedef öğeyi ortadaki öğeyle karşılaştırır. Bu işlem, hedef eleman bulunana veya arama aralığı boşalana kadar tekrarlanır.

Nasıl çalışır

1. Sıralanmış listenin tamamıyla başlayın.
2. Geçerli arama aralığının ortadaki öğesini bulun.
3. Ortadaki öğeyi hedef değerle karşılaştırın.
4. Ortadaki eleman hedef değere eşitse arama başarılıdır.
5. Ortadaki eleman hedeften büyükse, aralığın sol yarısında arama yapın.
6. Ortadaki eleman hedeften küçükse, aralığın sağ yarısında arama yapın.
7. Hedef öğe bulunana veya arama aralığı boşalana kadar 2-6 arası adımları tekrarlayın.

Örnek

Sıralanmış bir tamsayı listesi düşünelim ve ikili aramayı kullanarak 34 sayısını bulmak istiyoruz.

Sıralı Liste: {12, 23, 34, 45, 56, 67, 89, 90}

1. Tüm listeyle başlayın.
2. Orta eleman: 56(konum 4). 34 ile karşılaştırın.
3. 56, 34'ten büyüktür. Sol yarıda arama yapın.
4. Yeni orta eleman: 23(konum 1). 34 ile karşılaştırın.
5. 23, 34'ten küçüktür. Sağ yarıda arayın.
6. Yeni orta eleman: 45(konum 3). 34 ile karşılaştırın.
7. 45, 34'ten büyüktür. Sol yarıda arayın.
8. Yeni orta eleman: 34(konum 2). Hedef bulundu.

C++'da Örnek Kod

#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;  
}  

Verilen örnekte, binarySearch işlev, sıralanmış bir tamsayılar listesinde 34 sayısını bulmak için kullanılmıştır. Sonuç, listedeki 34 konumu(konumlar 0'dan başlar) veya sayı bulunamazsa -1 olur.