Arama algoritması

bilgisayar biliminde özelliklere göre istenilen bilgileri bulan algoritmalardır

Arama algoritmaları, bilgisayar biliminde seçili özelliklere göre istenilen bilgileri bulan algoritmalardır. Listeler, metinler ve şekiller üzerinde çalışırlar.

TürleriDüzenle

İkili arama algoritmasıDüzenle

Aranılan diziyi ikiye bölecek şekilde bir eleman seçilir. Sağındaki ve solundakilere bakılır. Algoritmanın çalışması için dizinin sıralı olması koşulu bulunmaktadır. Bu şekilde aranan sayı bulunana kadar işlem yapılır. Algoritmanın çalışması örnek üzerinden şu şekilde açıklanmıştır:

[1,2,4,7,9,11,15]

şeklinde bir dizi verilmiş olduğunda, aradığımız sayının da 4 olduğunu kabul ettiğimiz takdirde, dizinin eleman sayısı 7'dir. Bu durumda ortadaki eleman 4. eleman olarak seçilir ve 7 sayısı ile aranan sayı kontrol edilir. 4<7 olduğu için 4. elemanın solundaki sayılara bakılır:

[1,2,4]

şeklinde elde edilen yeni alt dizinin üzerinde algoritma yeniden çalıştırılır. Dizinin eleman sayısı 3'tür ve ortadaki elemanı 2. eleman olarak seçilir. Eleman değeri 2'dir ve aranan değer 4 ile karşılaştırılır. 4>2 olduğu için 2. elemanın sağ tarafında arama devam eder:

[4]

Tek başına aranan elemanın bulunduğu 4 değeri kaldığından dolayı, bu değer ile aranan değer karşılaştırıldığında aranan değere ulaşılmış olur.

Enine arama (Sığ öncelikli arama)Düzenle

Bütün çizge aramalarında ve özellikle ağaç aramalarında daha sık kullanılır. Başlangıç düğümüne yakın düğümlerin dolaşarak yoluna devam eder. Bir seviye uzaklaşmadan önce, o seviyeye kadar olan bütün düğümleri dolaşmış olması gerekir. Örneğin; ağaç araması sırasında, her satırda soldan sağa olmak üzere sıra ile bulana kadar arama yapar. Aranan düğüme ulaşmadan önce, aranan düğüm ile başlangıç düğümü arasındaki seviyelerde bulunan bütün düğümleri dolaşmak zorunda olması gibi bir dezavantajı vardır. Bu durum, algoritmanın hedefi bulmasını geciktirir. Resimdeki öncelik A-B-C-D-E-F-G-H-I-İ-J

Ayrıca ağaç olmayan bir çizgede de kullanılabilir. Örneğin aşağıdaki şekilde 1'den başlanarak dolaşılması halinde, öncelik 1-2-5-3-4-6 olacaktır.

Derin Öncelikli Arama (Depth First Search-DFS)Düzenle

Ağaç yapılarında kullanılır. Arama işlemine, Yukarıdan aşağıya sol öncelikli olarak arama yapar. Resimdeki aramada öncelik A-B-C-D-E-F-G-H-I-İ-J şeklindedir.

Enine arama algoritmasında verilen örnek grafın aynısı derin öncelikli olarak aransaydı, muhtemel arama sıralamalarından birisi 1-5-4-6-2-3 olabilirdi

Ayrıca bakınızDüzenle

Dış bağlantılarDüzenle