İkili Arama (Binary Search) Algoritması Nedir? Adım Adım Uygulamalı Örnek ile Detaylı Anlatım

tarihinde gönderilmiş tarafından

Algoritmaların çalışma prensibini anlamak için sıkça kullanılan ve temel algoritmalardan biri olan İkili Arama (Binary Search) algoritmasını inceleyelim. Bu algoritma, sıralı bir dizi içinde belirli bir öğeyi aramak için kullanılır ve oldukça verimli bir yapıya sahiptir.

İkili Arama (Binary Search) Algoritması Nedir?

İkili arama, sıralı bir dizi içinde bir öğeyi bulmak için kullanılan bir algoritmadır. Bu algoritma, veri kümesinin ortasındaki öğeyi seçerek arama yapar. Eğer aradığınız öğe ortadaki öğeye eşitse, arama tamamlanır. Eğer aradığınız öğe ortadaki öğeden küçükse, dizinin sol tarafında; büyükse, dizinin sağ tarafında aramaya devam edilir. Bu işlem, aranan öğe bulunana veya arama yapılacak öğe kalmayana kadar devam eder.

İkili Arama Algoritmasının Adımları

  1. Aradığınız değerin sıralı bir dizide olup olmadığını kontrol edin.
  2. Dizinin ortasındaki öğeyi seçin.
  3. Eğer ortadaki öğe aradığınız değerse, öğe bulundu.
  4. Eğer aradığınız öğe ortadaki öğeden küçükse, sol tarafta aramaya devam edin.
  5. Eğer aradığınız öğe ortadaki öğeden büyükse, sağ tarafta aramaya devam edin.
  6. Bu işlemi öğe bulunana kadar veya dizi boyutu 0 olana kadar tekrarlayın.

Örnek Üzerinde Binary Search Algoritması

Elimizde şu sıralı dizi olduğunu düşünelim:

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

Bu dizide aramak istediğimiz değer: 7

Adım 1:

Dizinin ilk ve son indekslerini bulalım:

  • İlk indeks: 0 (değer = 1)
  • Son indeks: 9 (değer = 19)

Orta indeks ise (0 + 9) / 2 = 4. Bu yüzden, dizinin 4. indeksindeki değere bakarız: 9

Aradığımız değer 7, ortadaki 9 değerinden küçüktür. Bu nedenle, dizinin sol tarafında aramaya devam ederiz (0. indeksten 3. indekse kadar).

Adım 2:

Yeni aralık: [1, 3, 5, 7]

Orta indeks bu sefer (0 + 3) / 2 = 1. Bu yüzden 1. indeksindeki değere bakarız: 3

Aradığımız değer 7, 3’ten büyüktür. Bu nedenle, dizinin sağ tarafında aramaya devam ederiz (2. indeksten 3. indekse kadar).

Adım 3:

Yeni aralık: [5, 7]

Orta indeks (2 + 3) / 2 = 2. Bu yüzden 2. indeksindeki değere bakarız: 5

Aradığımız değer 7, 5’ten büyüktür. Bu nedenle, dizinin sağ tarafında kalan tek indekse bakarız (3. indeks).

Adım 4:

Yeni aralık: [7]

Orta indeks: 3. İndekste bulunan değer 7‘dir ve bu bizim aradığımız değerdir.

Sonuç: 7 değeri dizinin 3. indeksinde bulundu.

Zaman Karmaşıklığı

İkili Arama Algoritması, diziyi her seferinde ikiye bölerek arama yaptığı için oldukça hızlıdır. Bu nedenle, zaman karmaşıklığı O(log n)‘dir. Bu, arama yapılacak eleman sayısı arttıkça, algoritmanın çalışma süresinin logaritmik olarak artacağı anlamına gelir. Bu da algoritmayı, özellikle büyük veri kümeleri üzerinde oldukça verimli hale getirir.

İkili Arama Neden Kullanılır?

  1. Verimli: Sıralı dizilerde çok hızlı sonuç verir, büyük veri kümelerinde dahi etkili şekilde çalışır.
  2. Basitlik: Algoritma, kolay bir mantığa dayanır ve anlaşılması basittir.
  3. Kullanım Alanı Geniş: Veri tabanı sorgularından, oyunlardaki yol bulma algoritmalarına kadar pek çok alanda kullanılabilir.

Özet

İkili arama, sıralı bir dizide belirli bir değeri aramak için kullanılan oldukça verimli bir algoritmadır. Her seferinde arama alanını ikiye bölerek ilerlediği için, özellikle büyük veri kümelerinde hızlı sonuç verir. Algoritmanın adımlarını anlamak ve uygulamak oldukça basittir, bu yüzden bilgisayar bilimlerinde sıkça kullanılan temel algoritmalardan biridir.

Görüntülenme Sayısı: 191