Bu yazımızda binary search (İkili arama) algoritması hakkında bilgiler vereceğiz.

Binary Search (İkili Arama) Algoritması Nedir ?

Binary Search (İkili Arama) algoritması, aranacak değerin bulunabileceği veri yapısının ortasından başlayarak veri yapısını ikiye bölerek arama yapma yöntemidir. Veri yapısının her bölümünde, aranacak değerin bulunabileceği bölüm belirlenir ve tarama o bölüme odaklanır. Bu yöntem ile veri yapısı boyutu büyüdükçe arama zamanı logaritmik olarak artar ve performans daha hızlı bir şekilde korunur.

Binary Search algoritmasının en önemli şartı veri yapısının sıralı olmasıdır. Eğer veri yapısı sıralı değilse, Binary Search algoritması çalışmaz. Veri yapısı sıralı olduğunda, algoritma, aranacak değerin bulunabileceği bölümü bulana kadar veri yapısını ikiye böler ve her bölümde arama yapar. Veri yapısının boyutu küçüldükçe arama zamanı azalır ve aranacak değer bulunana kadar devam eder.

Binary Search (İkili Arama) Algoritması Nasıl Kullanılır ?

Binary Search (İkili Arama) Algoritması, veri yapısı olarak sıralı bir dizi veya liste kullanılır. Aşağıdaki adımlar bu algoritmanın nasıl kullanılacağını gösterir:

  1. Başlangıç: Veri yapısının ortasındaki elemanın indeksi belirlenir ve aranacak değerle karşılaştırılır.
  2. Eşit: Eğer veri yapısındaki ortadaki eleman aranacak değere eşit ise, arama işlemi tamamlanır ve ortadaki elemanın indeksi döndürülür.
  3. Küçük: Eğer aranacak değer ortadaki elemandan küçük ise, veri yapısının sol tarafı aranır. Bu işlem aynı şekilde veri yapısının ortasındaki eleman ile aranacak değerin karşılaştırılması şeklinde devam eder.
  4. Büyük: Eğer aranacak değer ortadaki elemandan büyük ise, veri yapısının sağ tarafı aranır. Bu işlem aynı şekilde veri yapısının ortasındaki eleman ile aranacak değerin karşılaştırılması şeklinde devam eder.

Arama işlemi veri yapısının boyutu küçüldükçe sürer ve aranacak değer bulunana kadar devam eder. Bulunamazsa, veri yapısında aranacak değer bulunmamıştır.

Bu yazı dikkatini çekebilir.   Yığın Veri Yapısı (Stack)

Binary Search (İkili Arama) Algoritması Zaman Karmaşıklığı

Binary Search (İkili Arama) Algoritmasının zaman karmaşıklığı O(log n) dir. Bu, veri yapısındaki eleman sayısı arttıkça arama zamanı logaritmik olarak artması anlamına gelir.

Bu, veri yapısının boyutu küçüldükçe arama işleminin hızlandığı ve veri yapısının büyüdükçe arama işleminin yavaşladığı anlamına gelir. Bu, veri yapısı büyüdükçe arama işleminin zaman karmaşıklığının logaritmik olarak artması nedeniyle büyük veri yapıları için de uygun bir arama algoritmasıdır.

Binary Search (İkili Arama) Algoritması Örnek Kod

#include <stdio.h>

// Veri yapısındaki elemanlar
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

int binary_search(int arr[], int x, int l, int r) {
  // Arama işlemi sonuçsuz kaldıysa döndür
  if (r >= l) {
    int mid = l + (r - l) / 2;

    // Eşit: aranacak değer ortadaki elemandan eşitse döndür
    if (arr[mid] == x)
      return mid;

    // Küçük: aranacak değer ortadaki elemandan küçükse sol tarafı ara
    if (arr[mid] > x)
      return binary_search(arr, x, l, mid - 1);

    // Büyük: aranacak değer ortadaki elemandan büyükse sağ tarafı ara
    return binary_search(arr, x, mid + 1, r);
  }

  // Arama sonuçsuz kaldıysa -1 döndür
  return -1;
}

int main(void) {
  int n = sizeof(arr) / sizeof(arr[0]);
  int x = 4;
  int result = binary_search(arr, x, 0, n - 1);
  if(result == -1)
    printf("Aranacak eleman bulunamadı\n");
  else
    printf("Aranacak eleman indeksi: %d\n", result);

  return 0;
}

Çıktısı :

Aranacak eleman indeksi: 3

Bu yazımızda binary search (İkili arama) algoritması hakkında bilgiler verdik. Diğer veri yapıları konulu yazılarımızı okumak için buraya tıklayabilirsiniz.