Veri Yapıları ve Programlama

12 - Arama Algoritmaları

Emre Can Yılmaz
emrecan@omu.edu.tr

Ondokuz Mayıs Üniversitesi

2026

Arama Algoritmaları

Bir dizide, listede veya veri kümesinde belirli bir değerin bulunup bulunmadığını öğrenmek sık karşılaşılan bir işlemdir.

Örneğin:

  • Öğrenci numarası listede var mı?
  • Bir ürün kodu stok listesinde bulunuyor mu?
  • Bir kelime metin içinde geçiyor mu?

Arama algoritmaları, bu tür sorulara sistematik biçimde cevap vermek için kullanılır.

Bu Derste

  • Doğrusal aramanın nasıl çalıştığını inceleyeceğiz.
  • İkili aramanın neden sıralı veri gerektirdiğini göreceğiz.
  • İki algoritmanın C ile uygulanışını karşılaştıracağız.
  • Zaman karmaşıklığı açısından aralarındaki farkı değerlendireceğiz.

Temel Problem

Elimizde şu dizi olsun:

2, 4, 0, 1, 9

Aranan değer: 1

Soru:

  • Bu değer dizide var mı?
  • Varsa hangi indiste yer alıyor?

Doğrusal Arama Ne Zaman Kullanılır?

Doğrusal arama özellikle şu durumlarda uygundur:

  • Veri kümesi küçükse
  • Veri sıralı değilse
  • Ön hazırlık yapmadan doğrudan arama yapılacaksa
  • Veriye yalnızca sırayla erişilebiliyorsa

Doğrusal arama basittir; ancak büyük veri kümelerinde yavaş kalabilir.

Doğrusal Arama Nasıl Çalışır?

Aşağıdaki dizide k = 1 değerini arayalım.

Doğrusal Arama: Karşılaştırma

İlk elemandan başlanır.

Her eleman aranan değerle karşılaştırılır: array[i] == k

Eğer eşleşme varsa ilgili indis döndürülür.

Doğrusal Arama: Sonuç

Eşleşme bulunursa arama biter.

Eşleşme yoksa bir sonraki elemana geçilir.

Dizi sonuna kadar eşleşme bulunamazsa -1 döndürülür.

Doğrusal Arama Algoritması

  1. Dizinin ilk elemanından başlanır.
  2. Her eleman aranan değerle karşılaştırılır.
  3. Eşleşme varsa elemanın indisi döndürülür.
  4. Eşleşme yoksa sonraki elemana geçilir.
  5. Dizi sonuna kadar eşleşme bulunamazsa -1 döndürülür.

C ile Uygulama: Doğrusal Arama

#include <stdio.h>

int search(int array[], int n, int x) {
  for (int i = 0; i < n; i++) {
    if (array[i] == x) {
      return i;
    }
  }

  return -1;
}

int main(void) {
  int array[] = {2, 4, 0, 1, 9};
  int x = 1;
  int n = sizeof(array) / sizeof(array[0]);

  int result = search(array, n, x);

  if (result == -1) {
    printf("Eleman bulunamadı\n");
  } else {
    printf("Eleman %d indisinde bulundu\n", result);
  }

  return 0;
}

Doğrusal Aramanın Maliyeti

Doğrusal aramada yapılacak karşılaştırma sayısı, aranan değerin dizideki konumuna bağlıdır.

Durum Açıklama Karmaşıklık
En iyi durum Aranan değer ilk elemandadır O(1)
Ortalama durum Aranan değer dizinin ortalarındadır O(n)
En kötü durum Aranan değer sonda ya da dizide yoktur O(n)

Doğrusal Aramanın Sınırı

Dizi küçükse doğrusal arama yeterli olabilir.

Ancak dizi çok büyükse her elemanı sırayla kontrol etmek maliyetli hale gelir.

Örneğin 1.000.000 elemanlı bir dizide, aranan değer en sondaysa 1.000.000 karşılaştırma gerekebilir.

Bu durumda daha etkili bir yöntem düşünülebilir.

İkili Arama İçin Ön Koşul

İkili arama yalnızca sıralı dizilerde doğru çalışır.

Örnek sıralı dizi:

3, 4, 5, 6, 7, 8, 9

Bu dizide küçük değerler solda, büyük değerler sağdadır.

Bu düzen sayesinde arama alanının hangi yarısının eleneceğine karar verilebilir.

Sıralı Olmayan Dizide Neden Çalışmaz?

Sıralı olmayan bir dizi düşünelim:

8, 3, 10, 1, 6

Aranan değer: 1

Ortadaki değer 10 olsun.

1 < 10 olduğu için sol tarafa geçmek doğru gibi görünebilir.

Ancak dizi sıralı olmadığı için 1 değerinin solda olacağı garanti değildir.

İkili Aramanın Temel Değişkenleri

İkili aramada üç temel indis kullanılır:

Değişken Anlamı
low Arama aralığının başlangıç indisi
high Arama aralığının bitiş indisi
mid Arama aralığının orta indisi

Dikkat edilmesi gereken ayrım:

  • mid: indis
  • array[mid]: o indisteki değer

Orta İndisin Hesaplanması

Orta indis şu şekilde hesaplanır:

mid = low + (high - low) / 2;

Bu yazım, şu ifadeye göre daha güvenlidir:

mid = (low + high) / 2;

Çünkü çok büyük dizilerde low + high toplamı tam sayı taşmasına neden olabilir.

İkili Arama Nasıl Çalışır?

Sıralı dizimiz:

3, 4, 5, 6, 7, 8, 9

Aranan değer: x = 4

Arama Aralığını Belirle

Başlangıçta arama tüm dizi üzerinde yapılır.

  • low = 0
  • high = n - 1

Orta Değeri Bul ve Karşılaştır

Örnek durumda:

  • low = 0
  • high = 6
  • mid = 3
  • array[mid] = 6

Aranan değer 4, orta değer 6dan küçüktür.

Bu nedenle arama sağ tarafta değil, sol tarafta devam eder.

Arama Aralığını Daralt

x < array[mid] olduğu için sağ taraf elenir.

Yeni arama aralığı: high = mid - 1;

mid tekrar aralığa dahil edilmez; çünkü array[mid] zaten kontrol edilmiştir.

Bu tercih gereksiz tekrarları ve olası sonsuz döngüleri önler.

İşlemi Tekrarla

Yeni aralıkta tekrar orta indis hesaplanır.

low <= high olduğu sürece arama devam eder.

Elemanı Bul

Eğer array[mid] == x koşulu sağlanırsa aranan değer bulunmuştur.

Bu durumda mid indisi döndürülür.

İkili Arama Algoritması

  1. low değerini dizinin ilk indisi olarak belirle.
  2. high değerini dizinin son indisi olarak belirle.
  3. low <= high olduğu sürece:
    • mid indisini hesapla.
    • array[mid] == x ise mid değerini döndür.
    • array[mid] < x ise sağ yarıda ara.
    • array[mid] > x ise sol yarıda ara.
  4. Aralık kalmadıysa -1 döndür.

C ile Uygulama: İteratif İkili Arama

Aşağıdaki kod yalnızca binarySearch fonksiyonunu göstermektedir. Fonksiyonun nasıl çağrılacağı ilerleyen slaytta ortak main fonksiyonu ile gösterilecektir.

#include <stdio.h>

int binarySearch(int array[], int x, int low, int high) {
  while (low <= high) {
    int mid = low + (high - low) / 2;

    if (array[mid] == x) {
      return mid;
    }

    if (array[mid] < x) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
}

Alternatif Uygulama: Özyinelemeli İkili Arama

İkili arama özyinelemeli olarak da yazılabilir.

Bu yaklaşımda her çağrıda arama aralığı küçültülür.

Aşağıdaki kod yalnızca binarySearch fonksiyonunu göstermektedir. Tam program için bu fonksiyon, ilerleyen slaytta verilen ortak main fonksiyonu ve #include <stdio.h> satırıyla birlikte kullanılabilir.

int binarySearch(int array[], int x, int low, int high) {
  if (high >= low) {
    int mid = low + (high - low) / 2;

    if (array[mid] == x) {
      return mid;
    }

    if (array[mid] > x) {
      return binarySearch(array, x, low, mid - 1);
    }

    return binarySearch(array, x, mid + 1, high);
  }

  return -1;
}

İteratif ve Özyinelemeli Yaklaşım

Her iki yöntem de aynı temel fikre dayanır: arama aralığını her adımda küçültmek.

Ancak uygulama biçimleri farklıdır.

Yaklaşım Özellik
İteratif Döngü kullanır
Özyinelemeli Fonksiyon kendisini tekrar çağırır
İteratif Genellikle daha az bellek kullanır
Özyinelemeli Çağrı yığını nedeniyle ek bellek kullanabilir

Ortak main Fonksiyonu

Aşağıdaki main fonksiyonu, verilen binarySearch fonksiyonuyla birlikte kullanılabilir.

int main(void) {
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int n = sizeof(array) / sizeof(array[0]);
  int x = 4;

  int result = binarySearch(array, x, 0, n - 1);

  if (result == -1) {
    printf("Eleman bulunamadı\n");
  } else {
    printf("Eleman %d indisinde bulundu\n", result);
  }

  return 0;
}

İkili Arama Zaman Karmaşıklığı

İkili aramada her adımda arama aralığı yaklaşık olarak yarıya iner.

Durum Açıklama Karmaşıklık
En iyi durum Aranan değer ilk orta elemandadır O(1)
Ortalama durum Arama aralığı birkaç kez ikiye bölünür O(log n)
En kötü durum Değer en son adımda bulunur ya da yoktur O(log n)

O(n) ve O(log n) Farkı

1.000.000 elemanlı bir dizide:

Algoritma En kötü durumda yaklaşık karşılaştırma
Doğrusal arama 1.000.000
İkili arama 20

İkili arama bu nedenle büyük ve sıralı veri kümelerinde daha avantajlıdır.

Doğrusal Arama ve İkili Arama Karşılaştırması

Özellik Doğrusal Arama İkili Arama
Sıralama gerekli mi? Hayır Evet
Çalışma biçimi Elemanları sırayla kontrol eder Arama aralığını ikiye böler
En iyi durum O(1) O(1)
En kötü durum O(n) O(log n)
Küçük veri için uygun mu? Evet Evet, fakat sıralama gerekir
Büyük ve sıralı veri için uygun mu? Daha yavaş kalabilir Daha uygundur

Sıralama Maliyeti

İkili arama hızlıdır; ancak yalnızca sıralı dizide çalışır.

Eğer veri sıralı değilse önce sıralama yapılmalıdır.

Bu nedenle şu soru önemlidir: Veri zaten sıralı mı?

Eğer veri yalnızca bir kez aranacaksa sıralama yapmak her zaman avantajlı olmayabilir.

Eğer aynı veri üzerinde çok sayıda arama yapılacaksa, veriyi sıralayıp ikili arama kullanmak daha anlamlı olabilir.

Tekrarlanan Değerler

Dizide aranan değerden birden fazla olabilir.

Örnek dizi: 2, 4, 4, 4, 9

Bu durumda doğrusal arama ilk karşılaştığı eşleşmenin indisini döndürür.

İkili aramada ise bulunan eşleşmenin ilk, son veya ortadaki tekrar olacağı garanti değildir.

İlk ya da son eşleşme özellikle isteniyorsa algoritma buna göre değiştirilmelidir.

Hazır Fonksiyon Notu: bsearch()

C standart kütüphanesinde ikili arama için bsearch() fonksiyonu bulunur.

Bu fonksiyon <stdlib.h> içinde tanımlıdır.

Ancak bsearch() kullanabilmek için:

  • Verinin sıralı olması gerekir.
  • Karşılaştırma fonksiyonu yazılması gerekir.
  • Dönen sonucun işaretçi olduğu bilinmelidir.

Bu derste algoritmanın mantığını öğrenmek için kendi ikili arama fonksiyonumuzu yazıyoruz.

Bulunamama Durumları

Her iki algoritmada da aranan değer bulunamayabilir.

Bu durumda genellikle -1 döndürülür.

Bu değer, geçerli bir dizi indisi değildir.

Bu nedenle “aranan eleman bulunamadı” anlamında kullanılabilir.

Başka Arama Algoritmaları

Arama algoritması seçimi, verinin yapısına bağlıdır.

Veri / Problem Türü Örnek Arama Yaklaşımları
Sıralı diziler İkili arama, Jump Search, Interpolation Search
Anahtar-değer verileri Hash tablosu ile arama
Ağaçlar Binary Search Tree üzerinde arama
Graflar Breadth-First Search, Depth-First Search
Metinler KMP, Boyer-Moore

Bu derste temel mantığı öğrenmek için doğrusal arama ve ikili arama yeterlidir.

Çalışma Soruları

  1. Doğrusal arama hangi durumlarda ikili aramaya göre daha uygun olabilir?
  2. İkili arama neden sıralı veri gerektirir?
  3. mid ile array[mid] arasındaki fark nedir?
  4. 1000 elemanlı bir dizide ikili arama en kötü durumda yaklaşık kaç adım sürer?
  5. Aynı veri üzerinde çok sayıda arama yapılacaksa hangi yaklaşım daha uygun olabilir?
  6. Dizide aynı değerden birden fazla varsa arama sonucu nasıl yorumlanmalıdır?

Özet

Bu derste iki temel arama algoritmasını inceledik.

  1. Doğrusal Arama
    • Elemanları baştan sona sırayla kontrol eder.
    • Sıralama gerektirmez.
    • En kötü durumda O(n) maliyetlidir.
  2. İkili Arama
    • Arama aralığını her adımda ikiye böler.
    • Yalnızca sıralı dizilerde çalışır.
    • En kötü durumda O(log n) maliyetlidir.

Kapanış

Doğrusal arama basit ve genel bir çözümdür.

İkili arama ise sıralı veri üzerinde daha etkili bir çözümdür.

Bir arama algoritması seçerken verinin sıralı olup olmadığı, veri kümesinin büyüklüğü ve kaç kez arama yapılacağı birlikte düşünülmelidir.