Arama algoritması

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

Türleri

İkili arama algoritması
Ana madde: İkili arama algoritması

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)
Ana madde: Enine arama

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

Öncelik sırası 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.

Öncelik sırası 1-2-5-3-4-6

Derin Öncelikli Arama (Depth First Search-DFS)

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.

Öncelik sırası A-B-C-D-E-F-G-H-I-İ-J

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

Öncelik sırası 1-5-4-6-2-3

Ayrıca bakınız

Dış bağlantılar
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.