Cyber-Warrior.Org \ Doküman \ Programlama

2. ARAMA

Siralama adimindan sonra en önemli konu “arama” islemidir. Isim ve adres bilgilerini

saklayan bir programda, bilgilerin siralanmasive aranmasialgoritmalarina ihtiyaç duyulur.

Örnegin;Ankara’da yasayan “F” harfi ile baslayan isimlerin listelenmesi istenebilir.

Arama isleminin hizliolmasiiçin genellikle programlar verileri önce siralarlar.

Siralama ve arama islemleri, uygun algoritma seçilerek hizlive etkin olarak yapilir. Ayrica

siralilistede minimum ve maksimum deger otomatik olarak bulunmusolur. Listenin en

basindaki eleman en küçük degere, liste sonundaki eleman ise en büyük degere sahiptir.

2.1. Sirali(Ardisik) Arama

Siraliarama (sequential search) listedeki tüm bilgileri tarama yöntemidir. Liste, bagli

liste veya dizi olabilir.

Evinizin kapianahtarinikaybettiginizde, siraliarama yöntemini kullanarak anahtari

aramak istersek, apartmandaki tüm odalaritek tek arama yolu ile yapabiliriz. Eger anahtar ilk

odalarda ise hizlibir sekilde anahtarinizibulursunuz. Yani küçük listelerde bu arama

yönteminin yavasliginihissetmezsiniz bile. Tüm sehri aramaniz gerektigini düsünün, arama

hiziçok yavasolurdu.

Aramayiister baslangiçtan, isterseniz listenin sonundan baslatabilirsiniz. Aranan bilgi

bulundugunda arama islemi sona erer.

2.2. Ikilik Arama

Ikilik arama† (binary search) siralihaldeki bir listede hizlica arama yapmamizisaglar.

Uzun liste ikiye bölünür, aranan bilgi hangi yarida ise, o yariiçinde arama yapilir. Sayi

bulunana kadar liste yariya bölünerek arama islemi devam eder.

On elemanlidizide 37 rakaminibulmak için, önce dizinin ortasindaki eleman olan 30

ile aramaya baslanir. 37 rakami30’dan büyük oldugu için sagtaraftaki yarida arama

yapilacaktir.

† Ikilik arama sadece siralihâldeki listeler içindir

Kalan bessayida ortadaki 59 ile aranan sayiolan 37 karsilastirir. Bu sefer de sol

tarafta arama yapilacaktir. Elimizde iki sayikaldi. Listedeki ilk eleman aranan sayiile

karsilastirilir. 37 rakamiüçüncü adimda bulunmusoldu. Siraliarama yönteminde olsaydi

altinciadimda arama bitecekti.

Ikilik arama yönteminin akissemasiniçiziniz. Test degerleri seçip, akissemanizi

deneyiniz.

“Yari” degiskeninin degeri bulunmasinda bir açik vardir. Eger “Sol ve Sag”

degiskenlerinin toplamitam sayidegiskenin sinirlarinigeçerse, program hata verip kapanir.

Bu sorunu nasil çözebilirisiniz?

Çözüm önerisi: (tamsayi () komutu ondaliklisayinin tam sayikisminiverir.)

2.3. Kiyma (Hashing) Yöntemi

Kiyma veya kiyim yöntemi (hashing search) yeri hemen hemen bilinen degerleri

bulmak için yapilmistir. Mesela, evinizin anahtarinigenellikle belli bir yere koyariz veya bir

yere asariz. Böylece bulmamiz kolaylasir. Programda aramayikolaylastirmak için elimizdeki

degerleri dizide belli yerlere atacagiz.

2.3.1. Kiyma Fonksiyonu

Bir veri yapisi(dizi veya bagliliste) içine degerler için, kiyma veya kiyim degeri

(hash value) hesaplanir. Kiyma degeri, kiyma fonksiyonu (hash function) yardimiile

bulunur. Kiyma fonksiyonu sayesinde, “aranan deger” tüm listede aranmasiyerine, belli bir

yerde aranarak bulunur. Örnegin bir arananDeger adlitam sayiyidizide aradigimizi

düsünelim; önce “kiyma degeri” bulunur:

KiymaDegeri = arananDeger % 5

//mod bulmak için baska bir yöntem:

KiymaDegeri = arananDeger – (tamsayi(arananDeger / 5) * 5)

Bu formül bize sayinin bese bölümünden kalan sayiyi“kiyma degeri” olarak verir.

Hangi sayisaklanmisolursa olsun kiyma degerleri 0, 1, 2, 3 veya 4 olabilir. Mesela 26

rakaminin 5’e bölümünden kalan degeri 1 oldugu için, 26 degerini dizinin 1. elemanina

atayabiliriz.

Uzun listelerde kiyma yöntemi ile arama çok hizlibir sekilde yapilabilir.

2.3.2. Kiyma Yönteminde Çakismalar

Kiyma fonksiyonu ile tek olan degere sahip bir sayiüretilir. Farkliliste elemanlarinin

aynikiyma degeri olabilir. Mesela, 7 ve 32 degerlerinin 5 ile bölümünden kalan sayi2’dir.

Aynikiyma degeri birden fazla sayida ise, buna çakisma (collision) denir. Çakismalari

kontrol altina almak için, aynikiyma degerine sahip olan elemanlar bir yapida toplanir. Iki

boyutlu bir dizi veya bagliliste içine çakisanlar tutulabilir.

Dizi veya bagliliste büyüyebilir veya hafizada fazla yer kaplamamasiiçin

kisaltilabilir.

2.3.3. Kiyma Yönteminde Arama

Degerler listeye kaydedildikten, sonra arama islemi kiyma fonksiyonu ile rahatlikla

yapilabilir. Aynikiyma degerine sahip elemanlar da kendi aralarinda taranir

Eger her elemanin kendi tek (unique) kiyma degeri var ise, kiyma fonksiyonu

sayesinde tek adimda arama islemi tamamlanir. Birden fazla kiyma degeri olan elemanlar ise

en azindan küçük bir liste halinde oldugundan, arama islemi fazla zaman kaybina neden

olmaz. Bu küçük listede siraliveya ikilik yöntemleri ile arama yapilabilir.

Kiyma arama yönteminde olusan alt listelerde nasil arama yapilabilir? Hangi arama

yöntemini tercih edersiniz?

Kisa listelerde kolay kodlanabilen “siraliarama”, hiz gerektiren daha büyük

listelerde “ikilik arama” tercih edilir.

Çok büyük verilerde “kiyma yöntemi” seçilebilir, ama kodlamasizordur. Önceden

degerleri veri yapisina yerlestirme gerekliligi ve alt listede farklialgoritma ile arama

kullanilmasigerektigi için kod yazimiuzun zaman alir.

ALINTIDIR!!!

kaynak=megep.meb.gov.tr