Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde bir bilgi kaynağı veya veri yapısı üzerinde problemi her adımda iki parçaya bölerek yapılan arama algoritmasının ismidir. Bu anlamda bazı kaynaklarda bölerek arama olarak da geçmektedir.
Arama algoritması, yapı olarak parçala fethet (divide and conquere) yaklaşımının bir uygulamasıdır.
Bu yazı kapsamında diziler üzerinde ikili arama işleminin nasıl yapıldığı anlatılacaktır. Ancak algoritma, diziler dışında çok farklı veri yapıları ve veri kaynakları için de kullanılabilir. Algoritmanın her durumda çalışması aşağıdaki şekildedir.
- Problemde aranacak uzayın tam orta noktasına bak
- Şayet aranan değer bulunduysa bit
- Şayet bakılan değer aranan değerden büyükse arama işlemini problem uzayının küçük elamanlarında devam ettir.
- Şayet bakılan değer arana değerden küçükse arama işlemini problem uzayının büyük elemanlarında devam ettir.
- Şayet bakılan aralık 1 veya daha küçükse aranan değer bulunamadı olarak bitir.
Yukarıdaki müsvedde kod (pseudo code) ele alındığında problem her seferinde aranan sayıya göre ortadan ikiye bölünmektedir. Bu anlamda problemin log2(n) adımda çözülmesi beklenir. Burada logaritmik fonksiyonların üssel fonksiyonların tersi olduğu ve her adımda problemi iki parçaya böldüğümüzü hatırlayınız.
Arama algoritmasının bir dizi üzerinde başarılı çalışması için dizinin sıralı olması gerekir. Yukarıdaki koddan anlaşılacağı üzere ortadaki elemana bakıldığında, aranan sayı ya bakılan sayıdan büyük ya da küçüktür. Dolayısıyla algoritmamız, ya bakılan sayıdan küçük olan sayılar arasında arama yapacak ya da büyük olan sayılar arasında arama yapacaktır.
Bu durumu örnek bir dizi (array) üzerinden açıklamaya çalışalım. Örneğin dizimiz aşağıdaki şekilde verilmiş olsun:
int a[10]={2,3,5,6,9,12,32,54,74,111};
Bu dizi üzerinde 10 eleman bulunduğuna göre aranan sayı her ne olursa olsun ilk bakılacak değer ortadaki değer olan (5. Değer) 12 sayısıdır.
Dizi üzerinde arama işlemi için örnek olarak 3 sayısını aradığımızı düşünelim. Ve aşağıdaki şekilde dizide arama işlemine devam edelim:
Ortadaki değere baktıktan sonra sayı küçük olduğu için altında kalan (solundaki) sayıların ortasındaki değere (yani 2. elemana) bakıyoruz.
Aradığımız sayı (yani 3) dizide baktığımız sayıdan küçük olduğu için arama işlemine yine baktığımız sayıdan küçük olan (solunda olan) sayılar ile devam ediyor ve ortadaki sayı olan dizinin 1. Elemanına bakıyoruz.
Aradığımız sayıyı bulmuş oluyoruz ve çalışmamız bitiyor.
Farklı bir örnek olarak aranan sayının 37 olduğunu (ve dizide olmayan bir sayı olduğunu) düşünelim. Çalışmamız, yine dizinin tam ortasındaki eleman ile başlayacaktır:
Aradığımız sayı baktığımız sayıdan büyük olduğu için dizinin bakılan değerden büyük elemanlarında aramaya devam ediyoruz. Bu alanın ortasındaki değer dizinin 7. Elemanı olur ve 54’tür.
Bu değer aradığımız 37 sayısından büyük olduğu için geri kalan sayılar arasından küçük sayılara bakıyoruz. Bu durumda geri kalan sayılarımız 12’den büyük ve 54’ten küçük sayılardır ve ortasındaki eleman 32’dir.
Sayımız 32 sayısından büyük (aradığımız sayı 37 idi) bu durumda bakılacak başka sayı kalmadığı için (hem 54 hem de 32 sayılarına baktık ve arada başka sayı bulunmuyor) çalışmamızı bitirip aranan sayının dizide olmadığını söyleyebiliriz.
Arama algoritmasını kodlarken yukarıda karşılaşacağımız bir problem, dizinin hangi elemanlarına bakıyor olduğumuz ve bu elemanların orta değerinin bulunmasıdır.
Bu problemin çözümü için dizide arama yapılan elemanlardan en küçük ve en büyük indisli sayıları tutmak genelde kolay bir çözüm sunar.
Aşağıdaki açıklamalar sırasında en küçük indis için kırmız, en büyük indis için yeşil ve orta değer için mavi renkler kullanılacaktır.
İlk örneğimiz olan 3 sayısını ararken indis değerlerimiz aşağıdaki şekildedir:
Dizide aranan sayının bulunabileceği en küçük indis 0 ve en büyük indis 10 olarak kabul edilirse
Dizide bulunan 5. Sayıya bakıyoruz (10 + 0) / 2 = 5. Ayrıca artık aradığımız sayının 5. Elemandan daha büyük olma ihtimali bulunmuyor. Dolayısıyla aranabilecek en büyük sayı 5. Elemandadır diyerek en büyük indisi dizinin 5. Elemanı olarak ayarlıyoruz.
Arama işlemine ortadaki sayı ile devam edeceğiz (5+0)/2 = 2 olduğu için 2. Elemana bakıyoruz.
Aradığımız sayı baktığımız sayıdan küçük olduğu için artık 5’ten büyük sayılara bakmanın bir anlamı yoktur diyerek en büyük indisi dizinin 2. Elemanı olarak atıyoruz. Baktığımız sayı aradığımız sayıya eşit olduğu için de sayıyı bulduk diyerek çalışmamızı bitiriyoruz.
İkinci örnek olan ve 37’yi aradığımız örnekteki indis değerlerine bakacak olursak. İlk olarak en büyük ve en küçük olarak dizinin ilk ve sonuncu elemanlarını alıyoruz.
Bakacağımız değer, arama işleminin yapıldığı uzaydaki orta değer olacağı için (10+0)/2 = 5 sonucuna göre dizinin 5. Elemanına bakıyoruz. Bu değer aradığımız değerden küçük olduğu için arama uzayının, bakılan değerden büyük olan kısmı ile devam ediyoruz. Ayrıca baktığımız bu değerden daha küçük sayıları artık aramanın anlamı olmadığı için en küçük indis olarak 5. İndisi atayabiliriz..
Artık aradığımız değerler 5 ile 10. Değerler arasında olduğuna göre bakacağımız değer (10+5)/2 = 7 olarak atanmalıdır. Aradığımız değer olan 37 , baktığımız değer olan 54’ten küçük olduğu için artık 54’ten büyük değerleri aranmayacak şekilde en büyük indisi 54 olarak atıyor ve orta değer olan (7+5) /2 = 6. İndisteki 32 değerine bakıyoruz.
Arama işlemi bu adımda bitiyor çünkü aranan sayı olan 32 ile en büyük değer olan 54 arasında başka bir sayı olamayacağına göre ve aradığımız değer bu arada olacağına göre işlem bitebilir.
Yukarıda verilen örnek üzerinde çalışabilecek C kodunu aşağıdaki şekilde yazabiliriz:
Yukarıdaki kodda, dikkat edilecek bir püf noktası 7. Ve 8. Satırlardaki -1 ve 10 değerleridir. Bunlar arama işleminin arasında yapılacağı indisleri belirten en büyük indis ve en küçük indis değerleridir. Bu değerler dikkat edildiği üzere dizinin tanımlı olduğu indislerin dışındadır. Yani yukarıda 10 elemanlı bir dizi söz konusudur dolayısıyla bu dizinin -1 ve 10 numaralı elemanları yoktur.
Yukarıdaki kodda bu şekilde bir değerden başlamanın sebebi, dizi üzerinde arama yapılırken köşede kalan elemanların aranmamasıdır. Okuyucu dilerse yukarıdaki kodda, eb = 9 yazarak 123 değerini veya ek=0 yazarak 2 değerini aratmayı deneyebilir.
Algoritmanın Performansı
İkili arama algoritması (binary search algorithm) arama yaptığı uzayı her adımda iki eşit parçaya bölerek devam ettiği için O(log2(n) ) performansına sahiptir. Elbette arama algoritması en iyi ihtimalle ilk baktığı değeri bulabilir, bu durumda 1 erişim sonuca erişmek için yeterli olacaktır.
Algoritmanın sıralı olmayan, karışık bir dizi üzerinde çalışması için öncelikle dizinin sıralanması gerekir. Bu işlem en iyi sıralama algoritmasına göre ( birleştirme sıralaması (merge sort) veya hızlı sıralama algoritması (quick sort) ile) O(nlog2(n)) adımda yapılmaktadır. Dolayısıyla dizinin önce sıralanması ardından da ikili arama algoritmasına göre aranması işlemi için
n log2(n) + log2(n)
= log2(n) (n+1)
İşlem yapılması gerekecektir. Öte yandan çok daha kötü bir performansa sahip olan doğrusal arama (linear search) algoritması aynı işlemi O(n) performansı ile yapabilmektedir. Dolayısıyla karışık bir dizi içerisinde arama işlemi yapılacaksa, doğrusal arama algoritması her zaman için en basit ve hızlı algoritmadır.
Bu durumun bir istinası, arama işleminin sürekli yapılması durumudur. Örneğin bir bankada, bankamatiğe müşterinin her kartını takışında kaydının arandığını düşünelim. 10 milyon müşterisi bulunan bir banka için, müşterinin her aranması en kötü ihtimalle 10 milyon arama gerektirecektir.
Öte yandan veriyi bir kere sıraladıktan sonra her arama işlemi için sadece log2(10.000.000) ~24 işlem yeterli olmaktadır. Bu aramanın gerçekleştirilebilmesi için gereken sıralama maliyeti ise :
n log2(n) = 10.000.000 log2( 10.000.000) = 24.000.000
işlem gerektirmektedir. Dolayısıyla bu bankada 24’ten fazla arama gerekiyorsa (ki 10 milyon müşterisi bulunan bir banka için bir gün içerisinde binlerce kere müşteri bilgisine erişilmesi gerektiğini kabul edebiliriz). 25. Aramadan sonraki aramalarda sıralama maliyeti çıkarılmış ve performans olarak avantajlı hale geçilmiş olunur.
C++ dili
Gelen bir istek üzerine yukarıdaki kodun aynısını C++ diline çevirerek aşağıda yayınlıyorum. Aşağıdaki kodun görüleceği üzere C dilinde yazılmış olan yukarıdaki koddan bir farkı yoktur. Sadece ekran çıktılarının printf yerine cout olarak değiştirilmesi yeterlidir.
C# dili
Aynı kodu C# (csharp) dilince çevirdiğimizde aşağıdaki kodu yazmak mümkündür (Visual Studio 2008 Express Edition ile test edilmiştir):
JAVA ile
Aynı kodun java ile kodlanmış hali aşağıdadır:
Merhaba hocam,int a[5]={1,2,3,4,5}; binary search kodunda while(eb-ek>1) yazdıgımızda aratılan sayi olarak ” 1 ” dersek sayi bulunamadi diyo,bu seferde eb-ek>=1 yazdıgımda sayıyı buluyo,ama dizideki olmayan bi sayıyı arattıgımda ise ekran cıktısı durmuyo ve surekli devam ediyo(break kodu olmasına ragmen).dizideki ilk sayıyı bulma sorununu nasıl halledebilirim sizce? simdiden tesekkurler..
Bahsettiğiniz kodu farklı bir yazıya yazmışsınız. Sorunuz üzerine yeni bir yazı ekledim (yukarıdaki yazı) ve sorunuzun çözümü olabilecek kodu kodlayıp açıklamasını yukarıda anlatmaya çalıştım. Yorumunuzu da buraya taşıdım.
Ben yukarıdaki kodda, bahsettiğiniz durumları denedim ve hatasız olarak çalıştı. Bir kere daha deneyip bir hata tespit ederseniz ya da anlaşılmayan bir nokta kalırsa lütfen mesaj yazınız.
başarılar
Hocam sorunu simdi anladım.ben ek=0 aldıgım icin ilk degerde bulamıyor diomuş.sizin kodunuza baktıgımda ek=-1 aldıgında simdi kod tamamiyle dogru calısıyor.cok tesekkur ederim iyi calısmalar..
çok işime yaradı hocam çok sağolun,gerçekten çok anlaşılır yazıyorsunuz.
http://elifinciyel.blogspot.com
cok guzel bir baylasim sizden bir istegim olacak bu kodlarin c++ dilinde olani var mi acaba onuda baylasabilirmisiniz
Aynı kodu C++, C# ve JAVA için yeniden yazıp yukarıdaki yazıya ekledim. Göreceğiniz üzere kodda çok ufak değişiklikler yapmak yeterlidir.
başarılar
hocam burda bayrak değeri nedir
bayrak değişkeni (flag) programlama sırasında kullanılan ve bir döngüde denenen ihtimallerin hiçbirisi olmaması durumunda sonucun etkilendiği değişkendir.
Basitçe bir döngü içerisinde birden fazla ihtimali test etmek istiyorsunuz. Bu değerlerden birisi testi bozuyorsa işlem kolaydır ve döngüden hemen çıkılabilir ama şayet hiçbirisi bozmuyorsa bu durumu bulmak için döngünün sonuna kadar beklemek gerekir.
Yukarıdaki kodda da bayrak değeri şayet 0 girip 0 çıkıyorsa aranan değer bulunamadı mesajı basabiliriz. Benzer bir uygulama asal sayı bulan kodda da bulunmaktadır.
Hocam Paylaşımlarınız için sağol… Birde şu dörtlü arama hakkında biraz bilgi verebelir misiniz? Ben yazmaya çalıştım bazı sayılarda sonsuz döngüye giriyor…
Hocam öncelikle cok tesekkürler bilgi icin,
benim kafama takilan bir soru var.
Bu orta degeri bulurken siz (10 + 0) / 2 yapiyorsunuz ve 5.Deger olarak
12 yi aliyorsunuz.
Ama asagidaki linkte, indis degerlerini aliyor, yani (9 + 0) / 2 = 4,5 yapiyor,
bunu da 4 degerine yuvarliyor ve 4. Indis olan 19 degerini orta deger olarak
kabul ediyor.
Bununla ilgili bir aciklama yapabilir misiniz?
(Dipnot : Bir de paypal bagis butonu koyarsaniz, faydasi olacagini düsünüyorum)
Tesekkürler
aslında tam olarak (10+0)/2 değil. Konu anlatım kısmında dizi indisleri için sayma sayıları kullanılmıştır. Burada dizi boyutu 10 olarak kabul edilip 10. elemandan başlanarak işlenmiştir (9 değil).
Kod kısmına bakarsanız, eb = 10 ve ek = -1 olduğunu görürsünüz. Zaten (-1+10)/2 = 4,5 ile (0+9)/2=4,5 aynı indisten başlarlar.
Zaten yazı içerisinde bu konuya değinmiştim. Dilerseniz aynı koddaki eb değerini 9’dan veya ek değerini 0’dan başlatarak köşede kalan değerlerin aranmadığını görebilirsiniz.
başarılar
Hocam merhaba bu problemi rekürsif bi algoritma şeklinde yazabilir miyiz?
Elbette yazabiliriz:
arama(dizi d, sayi aranan){ if(d[ortadaki] > aranan) arama( dizinin solu, aranan) if(d[ortadaki]< aranan) arama(dizinin sağı, aranan) else return ortadaki // bulduk }Yukarıdaki şekilde müsvette kodu (pseudo code) yazılabilir. Burada ayrıca dizide olmama ihtimali bulunuyorsa, ortadaki değer hesaplatılırken ilave bir kontrol ile dizi boyutunun 0 olması durumu kontrol edilmeli ve şayet dizi boyutu 0 ise dizide aranan elemanın bulunmadığı söylenebilir
Hocam çok teşekkürler.Çok işime yaradı . Son derece anlaşılır yazmışsınız ellerinize sağlık .
Arkadaşlar ben bu yazılımda yeniyimde java kod da birşey aklıma takıldı. Bayrak variablini niye kullanıyoruz
yardımlarınız ve anlatımınız için çok tesekurler hocam her turlu konuda aradıklarımı sızde bulamk guzel tesekurler 🙂
7,4,3,8,1,5,4,2 dizisinin ikili arama sıralama ile sıralanmasının adımlarını gösteriniz. diye bir soruyla karşılaştım işin içinden çıkamıyorum. yardım ederseniz sevinirim.
bu terim : “ikili arama sıralama” nerede geçiyor? Benim bilebildiğim kadarıyla böyle bir sıralama algoritması yok. Bu soru ile nerede karşılaştınız?
Sayın hocam sorunun aslı budur.Ayrık matematik dersindeki ödevimdir. a şıkkını yaptım ama b şıkkı ile ilgili birşey bulamadım hocamızda anlatmadı yada ben anlamadım diyeyimde ayıp olmasın :-). nasıl olacak ki bu b şıkkı.
7,4,3,8,1,5,4,2 dizisinin
a. araya sokma sıralama ile sıralanmasının adımlarını gösteriniz
b. ikili arama sıralama ile sıralanmasının adımlarını gösteriniz
c. Araya sokma ve ikili arama sıralamada diziyi sıralamak için kaçar adet karşılaştırma yapılması gerektiğini belirtiniz?
Bir yerlerde bir hata olmuş sanırım. Tkerar ediyorum “ikili arama sıralamsı” diye bir sıralama algoritması ben bilmiyorum. Ya böyle bir sıralama algoritması yok ancak sorunun dizgisinde basımında bir hata olmuş, ya da benim bilmediğim böyle bir algoritma var. Belki hocanıza sorup, sıralama algoritmasnın orjinal ismini (tercihen ingilizcesini) öğrenirseniz daha çok yardımcı olabilirim. Bu haliyle birşey ifade etmiyor.
Başarılar
tamam hocam teşekürederim .ben onu öğrendikten sonra size tekrar dönerim inşAllah.
gökhan ikili arama ile o soruyu yapmayı hocamız bize söylemişti. İlk başta en ortadaki sayıya bakılıyor. Sonra böle böle en sağa ve en sola doğru ikili arama yapılıyor. İstenen sonuç bulunuyor.
Hasan Bey, bu bahsettiğiniz ikili arama algoritması. Yani sıralı bir listede aramaya yarar, sıralamaya değil. Gökhan Bey’in yazdığı ise sanırım sıralama algoritması. Sanırım bir yerlerde bir yanlışlık var.
Paylaştığınız bilgiler için teşekkür ediyoruz
hocam sızın kodun aynısı ile ikili arama degılde altılı arama yapmak ıstıyorum ama ben yapınca hata verdı, daha farklı kodlar mı gerekıyor yardımcı olabılır mısınız?
altılı arama algoritması ile tam olarak neyi kast ettiğinizi anlatırsanız yardımcı olmaya çalışayım. Ancak kabaca anlayabildiğim kadarıyla siz aranan diziyi 6 eşit parçaya bölmeyi hedefliyorsunuz. Bu durumda yukarıdaki kodunuz çok anlamlı değil. Yani bakilan değişkeninde orta noktayı tutmuşsunuz. Bunun yerine 6 adet nokta tutup bunlardan hangi ikisinin arasında olduğunu bulmanız gerekir. Basitçe
aralık = eb + ek
p1 = aralık / 6
p2 = aralık / 6 *2
p3 = aralık / 6 *3
p4 = aralık / 6 *4
p5 = aralık / 6 *5
şeklinde 5 nokta alacaksınız. Bu noktalar aralığı 6 eşit parçaya bölmüş olacak. ardından bu sayılardan hangi ikisi arasında olduğunu bulup yeni aralık olarak bu arayı işaretlemeniz gerekiyor.
Tabi sorunuzu doğru anladıysam.Yine de bunu neden yapmak istiyorsunuz? Yani nasıl bir avantaj hedefliyorsunuz?
hocam teşekkur ederım sorumun cevabını verdiniz.Proje ödevimin kapsamında altılı arama algoritması olusturmak bulunuyordu.araştırmama yardımcı oldunuz tekarar teşekkürler.
hocam çok teşekkür ederim bu temiz anlatım için. Çok yardımcı oldunuz.
hocam ben programlamada yeniyim..while(ib-ek>1) ile ne yapmaya çalışıyoruz ?
Yazıda açıklamaya çalışmıştım, eb = en büyük ve ek = en küçük ifadelerinin kısaltması olarak kullanılmış ve yazıdaki dizi üzerinde sınırları gösteren kırmızı (ek) ve yeşil (eb) işaretlerinin programlamadaki karşılığıdır. Burada aslında eb ile ek arasındaki fark 1’den fazlaysa hala aranacak değer var demek isteniyor, şayet aradaki fark 1 ise ve o tek farklı kutucuk da bizim aradığımız değer değilse o zaman eb’den büyük ve ek’den de küçük kutularda da aradığımız değer olamayacağı için arama işlemini bulamadık diyerek sonlandırabiliriz.
Çok teşekkürler hocam özellikle sınav döneminde paylaştıklarınız çok işimize yarıyor vikipedia’dan daha iyi içerikler üretmişsiniz 🙂
Teşekkürler güzel bir anlatım ve konu olmuş. Bu arada
else if (a[bakilan] > aranan)
{
eb = bakilan;
}
else
{
ek = bakilan;
}
şeklinde çalışıyor. Ters yazmışsın oraları galiba. Teşekkürler tekrardan