ALGORİTMALAR VE PROGRAMLAMA - Deneme Sınavı - 7

İkili arama

Özyinelemeli fonksiyon

Return

Zaman karmaşıklığı

O(n)

O(log(n))

Temel arama algoritmaları, ardışık arama (sequential search) ve ikili arama (binary search) algoritmalarıdır.

Ardışık arama, en temel arama algoritmasıdır. Bu algoritmanın çalışması için dizinin sıralı olmasına ihtiyaç bulunmamaktadır. Aranan eleman, sırasıyla dizinin her bir konumundaki eleman ile karşılaştırılır. Aranan elemanın değerinin dizinin elemanlarından
birisiyle aynı olduğu görülürse algoritma başarılı bir şekilde sonlandırılır. Eğer aranan
eleman dizinin içerisinde mevcut değilse, karşılaştırmalar dizinin ilk elemanından son
elemanına kadar sürecektir.

Ardışık arama algoritmasının çalışma mantığının anlatıldığı örnekte 5 elemanlı bir
dizi bulunmakta olup iki farklı elemanın dizinin içerisinde aranması gerçekleştirilmiştir.
Bu elemanlar sırasıyla 11 ve 8 sayılarıdır. İlk aranan 11 sayısının dizinin 3. elemanı olduğu
görülmektedir. Bu sebeple ilk arama 3. adımda başarı ile sonuçlandırılmış ve dizinin geride kalan elemanları kontrol edilmemiştir. Fakat daha sonra aranan 8 sayısı dizide bulunmamaktadır. Bu sebeple dizinin elemanlarının tamamının aranan eleman ile karşılaştırılması söz konusu olmaktadır. Şekilden de görüldüğü üzere 5 elemanlı bir dizi için en kötü
ihtimalde 5 adet karşılaştırma yapılması gerekmektedir. Şekil 6.1’deki örneğin C program
kodu ile ifade edilişi Örnek 6.1’de verilmiştir.

İkili arama, sıralı diziler üzerinde arama yapmak için kullanılan bir algoritmadır. Üzerinde arama yapılacak olan dizi sıralı durumda değilse, bu algoritmanın doğru çalışabilmesi için öncelikle dizinin sıralı hale getirilmesi gerekir.

İkili arama algoritması çalışmaya başladığında, ilk olarak dizinin ilk ve son elemanlarının konumları tespit edilir. Bu bilgilerden faydalanılarak orta elemanın konumu hesaplanır. Daha sonra, aranan eleman dizinin
orta elemanıyla karşılaştırılır ve ikisinin eşit olup olmadığına bakılır. Aranan eleman orta
elemana eşit ise arama başarılı bir şekilde sonlandırılır. Aksi takdirde, aranan elemanın
dizinin orta elemanından küçük veya büyük olma durumu incelenir. Aranan eleman orta
elemandan büyük ise, aramaya orta eleman ile son eleman arasındaki dizi elemanları ile
devam edilir. Tam tersi durum söz konusu ise, aramaya ilk eleman ile dizinin orta elemanı arasındaki dizi elemanları ile devam edilir. Bu işlem her tekrar edildiğinde ilk, orta
veya son elemanların konumlarının değişmesi söz konusu olabilir.

İkili arama algoritmasının çalışma mantığının anlatıldığı bu örnekte 7 elemanlı bir
dizi bulunmaktadır. Söz konusu dizi içerisinde 14 sayısının aranması söz konusudur. Algoritma çalışmaya başladığında ilk, orta ve son elemanların konumları belirlenmiştir. Şekilden de görüleceği üzere dizinin 4. konumundaki 12 sayısı orta elemandır. Daha sonra,
aranan eleman olan 14 sayısının orta elemana eşit, küçük veya büyük olması durumuna
bakılmaktadır. Bu sayı, orta elemandan büyük olduğu için aramaya dizinin ortası ile sonu
arasındaki elemanlardan devam edilir. Bu sebeple, ilk elemanın konum bilgisi güncellenmiştir ve bu güncelleme sonrasında orta elemanın konumu yeniden hesaplanmıştır. Daha
sonra, aranan eleman olan 14 sayısının yeni durumdaki orta eleman olan 20 sayısına eşit,
küçük veya büyük olması durumuna bakılmaktadır. 14 sayısının orta eleman olan 20’den
küçük olduğu anlaşıldığından aramaya dizinin ilk ve orta elemanı arasındaki elemanlardan devam edilir. Bu noktada da son elemanın bilgisi, bir önceki orta eleman olan 20 sayısından hemen önce gelen eleman olarak güncellenmiştir. Bu durumda, ilk ve son eleman
dizinin 5. konumunda yer alan 14 sayısıdır. İlk ve son elemanın konumlarının aynı olması
sebebiyle tekrar orta elemanın konumu hesaplanmıştır. Bu hesaplama sonucu ilk, orta ve
son elemanın konumlarının aynı duruma geldiği şekilde de görülmektedir. Orta eleman
olarak belirlenen dizinin 5. konumundaki sayının 14’e eşit olması sonucu, arama işlemi
başarılı bir şekilde sonlandırılacaktır. Şekilde de görüleceği üzere 14 sayısının aranması
sırasında 3 adet karşılaştırma işlemi yapılmıştır. Şekil 6.3’de ikili arama algoritmasının başarılı sonuçlandığı başka bir örnek daha verilmiştir. Bu örnekte, bir önceki örneğimizdeki
dizinin üzerinde 6 sayısının aranması söz konusudur.

Özyinelemeli (recursive)
fonksiyon: Özyinelemeli
fonksiyonlar, kendi içlerinde tekrar
kendilerini çağıran fonksiyonlardır.
Bu fonksiyonlarda bir bitiş koşulu
yer almaktadır. Fonksiyon, bu bitiş
koşulunu sağladığında adım adım
geriye değer döndürür ve sonlanır.

Zaman karmaşıklığı (time
complexity): Algoritmaların
sonuca ulaşması için gerekli olan
zaman hakkında bilgi veren bir
ölçüttür. En kötü durumdaki
zaman karmaşıklığı, algoritmanın
çalışmasının en uzun sürebileceği
durumu ifade etmek için kullanılır.

İkili arama algoritmasına yönelik C program kodu

İkili arama
algoritmasının
başarısızlıkla
sonuçlandığı bir örnek

bazı algoritmaların doğru çalışması için dizilerin sıralı durumda olması
gerektiği bilinmektedir. Sıralı durumda olmayan bir diziye bu türdeki bir arama algoritmasının uygulanması için dizinin öncelikle sıralı hale getirilmesi gerekir. Böyle bir durumda
ise sıralama ve arama algoritmalarının peş peşe çalışması söz konusu olur. Bu sebeplerle
probleme uygun arama algoritmasının seçilmesi önemlidir.

Çizgenin bir düğümünden başlanarak söz konusu komşu düğümlerinin ve onların da komşularının sırayla ziyaret edildiği algoritmaya enine arama algoritması denilmektedir.

D={1,2,3,4} kümesi ve şekle göre yönlü çizge örneğinden yola çıkarak K={(1,2), (1,3), (1,4), (2,3), (2,4), (3,2), (3,4)} kümesi elde edilir. K kümesi yedi adet kenar bağıntısını temsil eder.

Dijkstra algoritmasında kenarların ağırlık değeri sıfır veya sıfırdan büyük olmalıdır.
Diğer yandan düğümler arası geçişlerde en iyi çözümü sunan bu algoritma en kısa mesafeyi tespit etmek için kullanılmaktadır.