İkili Arama (Binary Search) Algoritması – Yazılım Karavanı | Bilişim – Teknoloji – Blog
İkili Arama (Binary Search) Algoritması
İkili arama, arama algoritmaların temelini oluşturmaktadır. Algoritmalar konusunda sık sık karşımıza çıkmakta olan ikili arama algoritmasını inceleyelim.
Örneğin bir sayı dizisini ele alalım. Her adımda gerçekleşmek üzere, diziyi ikiye bölerek ilerlemektedir. Parçala fethet mantığı ile çalışmakta olan algoritmamız yalnızca diziler üzerinde değil, birçok problemin çözümünde kullanılmaktadır. Kabaca algoritmadan bahsedecek olursak:
Araya Sokma (Insertion Sort) Algoritması
– Dizinin ortasını bul
– Aranan değer mi ? (çık veya devam et)
– Aranan değer küçükse alt parçaya git, büyükse üst parçaya git
– Aralık 1 değeri veya 1 den küçükse sonlandır.
şeklinde ilerlemektedir. Algoritmanın tam verimle çalışabilmesi için sayı dizisinin sıralı olması gerekmektedir.
Örnek bir dizi olarak aşağıdaki diziyi alalım ve 10 elamanını arayalım:
[0 10 20 30 40 50 60 70 80 90]
bu dizide ilk olarak bakılacak eleman 50 ‘dir
10 < 50 şartı sağlandığı için dizinin alt değerlerine bakılır. Bundan sonra üzerine çalışılacak elamanlar
[0 10 20 30 40]
şeklindedir. Yeniden ortadaki değere bakılır. Bu sefer ortadaki terim 20 ‘dir. 10 < 20 şartı sağlandığı için ortadan ikiye bölünen dizinin alt tarafına bakılmaya devam edilir. Bu sefer ki arama yapacağımız dizimiz
şeklindedir. Aradığımız eleman 1 indisli olan 10 = 10 şartını sağladığı için algoritmamız burada sonlanmaktadır. Aranan elaman dizide bulunduğu ve dizinin sıralı olduğu taktirde istenen sonucu elde edebiliyoruz. Anlaşılması ve kodlanması açısından kolay olan bir algoritma olması sebebiyle örneklerde ve günlük hayatta sık sık tercih edilmektedir. En iyi durumda algoritmanın ilk seferde aradığı elamanı bulmasıdır 1 adımda gerçekleşir. Öte yandan sıralı olmayan bir dizinin ilk önce sıralama algoritmaları kullanılarak sıralanması gerekmektedir. Maliyet kullanılan sıralama algoritmasına göre değişecektir. Hızlı Sıralama (Quick Sort) kullanılarak ikili arama algoritması n log_2 (n)+ log_2 (n) adımda gerçekleşir.
Algoritmanın örnek C kodu aşağıda verilmiştir:
Tags: AlgoritmalarAli Murat ÇEVİKBinary Search
Insertion sort algoritması temel sıralama algoritmalarından bir tanesidir. Algoritmanın mantığına göre elimizdeki A dizisinin elemanları arasında sıralama yapılmak istenildiğinde A...
Hızlı sıralama algoritması, sıralama algoritmalarında karşımıza sık sık çıkan bir algoritmadır. Böl ve yönet (divide and conquer) felsefesiyle çalışır. İlgili...
Bogo (Permutation) Sort Algoritması
Bogo Sort algoritması Permütasyon Sıralaması veya Saçma Sıralama olarak da adlandırılır. Verilen sayı dizisinin rastgele karıştırılması ile olası bütün ihtimalleri...
En temel sıralama algoritmalarından olan Bubble Sort (Kabarcık Sıralama) mantığını inceleyelim. Temel olarak ardışık iki eleman arasında karşılaştırma yaparak ilerler....