Merhaba arkadaşlar daha önce DrRacket ile Kabarcık Sıralamayı yapmıştık. Şimdi onun devamı niteliğinde bir de liste üzerinde ikili aramayı inceleyeceğiz.
İkili Arama Nedir?
Öncelikle ikili aramanın ne olduğuna bakalım. Basit bir arama algoritmasıdır. Sıralı diziler üzerinde çalışmaktadır. Eğer aradığımız değer listemizin ortasındaki değerden küçük ise ilk kısmı alacak eğer büyük ise ikinci kısmı alacak ve aynı işlemleri tekrar edecek ta ki ortadaki değer aradığımız değere eşit olana kadar.
Küçük bir örnek yapalım listemiz 2 5 9 12 14 23 34 olsun.
Aradığımız sayı da 5 olsun.
Adım 1) Listemizin ortasındaki sayı = 12 ile aradığımız sayıyı 5 i karşılaştırıyoruz. Küçük olduğu için sol kısmı alıyoruz.
2 5 9 12 kalıyor. İsterseniz 12 yi de bu listeden çıkarabiliriz çünkü küçük olduğunu söylemiştik. Yani: 2 5 9 kalıyor.
Adım 2) Kalan listedeki ortadaki eleman 5. Aradığımız eleman da 5 olduğu için bulup çıkacaktır.
Şimdi bunu DrRacket ile yazalım.
DrRacket İkili Arama Kodu
[the_ad id=”441″]
İkili Aramanın çalışması için listemizin sıralanması gerektiği için kabarcık sıralama algoritması ile birlikte kullanacağız.
(define (kabarcik L)(if (null? (rest L))L
(if (< (first L) (cadr L))
(cons (first L) (kabarcik (rest L)))
(cons (cadr L) (kabarcik (cons (first L) (cddr L))))
)
)
)
(define (kabarcikSirala N L)
(cond ((= N 1) (kabarcik L))
(else (kabarcikSirala (- N 1) (kabarcik L)))
)
)
(define (bubbleSort L)
(kabarcikSirala (length L) L)
)
(kabarcik '(6 10 4 8 7 1)) ; bir kere karşılaştırma yapıp yer değiştirme
(bubbleSort '(6 10 4 8 7 1)) ; kabarcık fonksiyonunun tekrarı ile tümünü sıralama
; İkili Arama Kodu Buradan Başlıyor Üst Kısım Kabarcık Sıralama Kodları..
(define (ikiliArama liste aranan)
(define orta (floor (/ (length liste) 2))) ;ortadaki sayının indeksi
(define ortadaki (list-ref liste orta)) ;indeksi verilen sayının değeri
(if (null? liste)
#f
(cond
((and (= (length liste) 1)
(not (equal? (first liste) aranan))) #f);aranana eşit değilse #f yazdır
((= ortadaki aranan) #t) ; eşit ise #t yazdır
((> ortadaki aranan) (ikiliArama (take liste orta) aranan)) ;büyükse üst kısmı al
((< ortadaki aranan) (ikiliArama (drop liste orta) aranan)) ; küçükse alt kısmı al
(else #f) ;değilse sayı yoktur #f yazdır.
)
)
)
(list-ref '(34 2 5 9 14 12 23) 2) ; bize verilen indisdeki sayıyı yazar
(ikiliArama'(2 5 9 12 14 23 34) 5) ; 5 i aradığımı varsa #t döndürür (sıralı) sırasız ise #f
(ikiliArama (bubbleSort '(34 2 5 9 14 12 23)) 12) ; sırasız ise sıralar daha sonra aradığımız varsa
;#t döndürür.
Çalışır vaziyeti aşağıdadır..
Gerekli kod açıklamlarını yorum satırları olarak ekledim. Zaten algoritma mantığını da açıklamıştım. Kodlar üzerinde hatalı ve anlaşılmayan yer olduğunda yorum yaparak ya da iletişim kısmından bana sorabilirsiniz. Umarım fayfalı olmuştur.
