Veri Yapıları ve Programlama

12 - Arama Algoritmaları

Emre Can Yılmaz

[email protected]

Ondokuz Mayıs Üniversitesi

2025

Arama Algoritmaları

Arama algoritması, bilgisayar bilimlerinde ve özellikle veri yapılarında, belirli bir öğeyi veya öğe grubunu bulmak amacıyla kullanılan bir algoritmadır.

Arama algoritmaları, veri içinde hızlı ve etkili bir şekilde istenilen bilgiyi bulmayı sağlar. Bu algoritmalar, verinin yapısına ve arama işlemine bağlı olarak çeşitli türlerde olabilir.

Arama algoritmalarının kullanım alanları:

• Web tarayıcılarında: İnternette bilgi ararken kullanılır.
• Veritabanlarında: Belirli kayıtları bulmak için kullanılır.
• Metin işlemede: Bir metin belgesinde belirli kelimeleri veya kelime öbeklerini bulmak için kullanılır. …

Kapsam

Bu ders kapsamında 2 arama algoritmasını öğreneceğiz.

1. Doğrusal Arama (Linear Search)
2. İkili Arama (Binary Search)

Doğrusal Arama (Linear Search)

Bu algoritma, veri yapısındaki her öğeyi sırasıyla kontrol eder ve aranan öğeyi bulana kadar devam eder. En basit arama algoritmasıdır. Küçük veya sıralanmamış veri kümeleri için uygundur.

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

Aşağıdaki listede k = 1 elemanını aramak için aşağıdaki adımlar izlenir.

1. İlk elemandan başlayın, k’yı her x elemanı ile karşılaştırın.

2. Eğer x == k ise, indeksi döndürür.

1. Aksi takdirde, bulunamadı olarak döndür.

C ile Gerçekleme

#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() {
  int array[] = {2, 4, 0, 1, 9};
  int x = 1;
  int n = sizeof(array) / sizeof(array[0]);

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

  (result == -1) ? printf("Element not found") : printf("Element found at index: %d", result);
}

İkili Arama (Binary Search)

İkili Arama, sıralanmış bir dizideki bir elemanın konumunu bulmak için kullanılan bir arama algoritmasıdır. Bu yaklaşımda, eleman her zaman bir dizinin bir bölümünün ortasında aranır.

⚠️ İkili arama yalnızca sıralanmış bir öğe listesi üzerinde uygulanabilir. Öğeler zaten sıralanmamışsa, önce onları sıralamamız gerekir.

İkili Aramanın Çalışma Prensibi

İkili Arama Algoritması aşağıda tartışılan iki şekilde uygulanabilir.

1. Döngüsel Yöntem
2. Özyinelemeli Yöntem

Bu algoritma böl ve fethet yaklaşımıyla çalışır.

Her iki yöntem için genel adımlar aşağıda tartışılmıştır.

1. Aramanın gerçekleştirileceği dizi:

Aranacak eleman x = 4 olsun.

2. İki işaretçiyi (pointer) en düşük ve en yüksek pozisyonlara yerleştirin: low ve high.

3. Dizinin ortadaki elemanını bulun, yani: mid = arr[(low + high) / 2] = 6.

4. Eğer x == mid ise, mid değerini döndürün. Aksi takdirde, aranacak elemanı mid ile karşılaştırın.
5. Eğer x > mid ise, x’i mid’in sağ tarafındaki elemanların ortadaki elemanı ile karşılaştırın. Bunu yapmak için low değerini mid + 1 olarak ayarlayın: low = mid + 1.

6. Aksi takdirde, x’i mid’in sol tarafındaki elemanların ortadaki elemanı ile karşılaştırın. Bunu yapmak için high değerini mid - 1 olarak ayarlayın: high = mid - 1.

7. Adım 3’ten 6’ya kadar olan adımları low ve high kesişene kadar tekrarlayın.

8. x = 4 bulundu.

C ile Gerçekleme

Döngüsel Yöntem (Iterative)

#include <stdio.h>

int binarySearch(int array[], int x, int low, int high) {
  // Repeat until the pointers low and high meet each other                                        .
  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;
}

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("Not found");
  else
    printf("Element is found at index %d", result);
  return 0;
}

Özyinelemeli Yöntem (Recursive)

#include <stdio.h>

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

    // If found at mid, then return it
    if (array[mid] == x)
      return mid;

    // Search the left half
    if (array[mid] > x)
      return binarySearch(array, x, low, mid - 1);

    // Search the right half
    return binarySearch(array, x, mid + 1, high);
  }

  return -1;
}

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("Not found");
  else
    printf("Element is found at index %d", result);
}

Çalışma Soruları

• Başka hangi arama algoritmaları var?
• Zaman karmaşıklığı nedir?

ÖZET

1. Doğrusal Arama:
   • Sıralanmamış, küçük elemanlı diziler için uygundur.
   • Verilere erişim sırayladır.
2. İkili Arama:
   • Böl ve Fethet yaklaşımını kullanır.
   • Yalnızca sıralanmış bir dizide çalışır.
   • Verilere erişim doğal olarak sırayla değildir.