İkili arama algoritması

Tanım

İkili Arama, sıralı bir dizide, belirli değerin bulunmasına yönelik bir algoritmadır. Bu teknikteki her bir adımda, aranan değerin, dizinin orta değerine eşit olup olmadığı kontrol edilir. Eşit olmaması durumunda aranan değerin orta değer tarafından ikiye ayrılan kısımlardan hangisinde olduğu kontrol edilir, aranan değeri içeren kısım bir sonraki adımda arama yapılacak dizi olur ve bu sayede arama yapılan listedeki eleman sayısı her adımda yarıya indirilmiş olur.

Bu algoritma ile N elemanlı bir dizide en fazla $\lceil \log _{2}N\rceil$ karşılaştırma yaparak aranan değerin yerini bulmak mümkündür.

Sıralı bir tam sayı dizisinde, aranan elemanın sırasını döndüren, yoksa -1 döndüren bir Java programı.

public class IkiliArama { // Java programının çalışması için gerekli olan public class.
  public static int ara(int[] dizi, int aranan) { // Üzerinde arama yapılacak olan dizi ve aranan sayı.

    int bas = 0; // Dizinin en başındaki elemanın sırası.
    int son = dizi.length - 1; // Dizinin en sonundaki elemanın sırası.
    
    // while bloğu içerisinde bas ve son değişkenleri her adımda değişeceği için burada kontrol ediyoruz. Tek bir eleman kalana kadar döngü devam ediyor.
    while (bas <= son) { 
      int orta = (bas + son) / 2;

      if (aranan < dizi[orta]) { // Aradığımız sayı orta elemandan küçükse, orta elemana ve daha büyüklerine bakmaya gerek yok.
        son = orta - 1; // Artık dizinin son elemanı, orta'nın bir eksiği.
      } else if (aranan > dizi[orta]) { // Aranan sayı orta elemandan büyükse, orta elemana ve daha küçüklerine bakmaya gerek yok.
        bas = orta + 1; // Artık dizinin baş elemanı, orta'nın bir fazlası.
      } else {
        return orta; // İki if bloğunda da girmiyorsa -küçük ya da büyük değilse- eşit olduğu anlamına geliyor. Sonuç olan bu değeri return ile döndürüyoruz.
      }
    }

    return -1; // while bloğundan çıkıldıysa, aranan sayı bulunamadı anlamına geliyor. -1 değeri döndürüyoruz.
  }
}

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.