C++ - İkili Arama (Binary Search) Algoritması

23 Ağustos 2017

İkili arama, sıralı bir dizide, belirli bir değerin bulunmasına yönelik bir algoritmadır. Bu algoritmayla her bir adımda, aranan değerin, dizinin orta değerine eşit olup olmadığı kontrol edilir. Eşit olmaması durumunda aranan değerin dizinin orta değerinden küçük veya büyük mü olduğuna bakılır. Eğer küçükse dizinin orta değeri dahil büyük kısmı yok sayılır ve küçük kısım yeni diziymiş gibi kabul edilir. Eğer büyükse dizinin orta değeri dahil küçük kısmı yok sayılır ve büyük kısım yeni diziymiş gibi kabul edilir. Aranan değeri içeren kısım bir sonraki adımda arama yapılacak yeni dizi olur. Böylelikle arama yapılan dizideki eleman sayısı her adımda yarıya indirilmiş olur.

Örneğin;

int B[10]= {1, 2, 13, 14, 15, 16, 27, 38, 49, 70};

NOT: İndis değeri sıfırdan başlar.
  • Aranan değer nedir? 1
  • 9/2=4.5 orta değer 4. indis 15'dir.
 1 2 13 14  15  16  27 38 49 70 
  • 15 aradığım değer mi? Hayır
  • 1 değeri 15 değerinden küçük veya büyük mü? Küçük
  • Yeni aranacak kısımdaki değerler:  1 2 13 14 
  • 3/2=1.5 orta değer 1. indis 2'dir.
 1  13 14 15 16 27 38 49 70
  • 2 aradığım değer mi? Hayır
  • 1 değeri 2 değerinden küçük veya büyük mü? Küçük
  • Yeni aranacak kısımdaki değerler: 
  • 0/2=0 orta değer 0. indis 1'dir.
 1  2 13 14 15 16 27 38 49 70
  • 1 aradığım değer mi? Evet

NOT: İkili arama algoritmasının karmaşıklığı O(log2n)'dir.

Programın Kodu

Programın Ekran Çıktısı
Aranan sayiyi girin: 1
Aranan sayi 0 indisli elemandir.

Hiç yorum yok:

Yorum Gönder