Giriş

Merhaba Arkadaşlar, Bugün “Her Programcının Bilmesi Gereken Algoritma” adlı bir diziye başlayacağım. Bu seride, Arama, Sıralama, Grafikler, Dizi vb. Çeşitli algoritmalara bakacağız.

Bugün, Arama Algoritması ile serinin ilk bölümü ile başlıyor. Her programcının bilmesi gereken 4 arama algoritmasına bakacağız. Şimdi Başlayalım.

Doğrusal Arama (Linear search)

Bilgisayar biliminde, doğrusal arama veya sıralı arama, bir liste içindeki bir öğeyi bulmak için bir yöntemdir. Bir eşleşme bulunana veya tüm liste aranana kadar listenin her bir öğesini sırayla kontrol eder.

Doğrusal aramada, listedeki hedef elemanı listenin ilk elemanından son elemana kadar sıralı sırayla ararız.

En İyi Durum: Hedef Değer, listenin ilk sırasındadır

En Kötü Durum: Hedef Değer, listenin son konumudur

Ne zaman kullanılmalı:

• Liste sıralanmadığında
• Liste küçük olduğunda

İkili Arama Algoritması (Binary Search Algorithm)

Bilgisayar biliminde, yarı aralıklı arama, logaritmik arama veya ikili kesme olarak da bilinen ikili arama, sıralı bir dizi içindeki bir hedef değerin konumunu bulan bir arama algoritmasıdır. İkili arama, hedef değeri dizinin orta elemanıyla karşılaştırır. Eşit değillerse, hedefin uzanamayacağı yarı elenir ve kalan yarıda arama devam eder, yine orta eleman hedef değerle karşılaştırılır.

İkili Aramada, liste sıralı bir sırada olmalıdır. Listenin ortasından değeri seçip karşılaştırarak hedef değeri aradık. Eşleşmezse, hedef değer orta elemandan küçükse, ilk yarı düşecek, aksi takdirde sonlanan yarı düşecektir. İşlem, hedef değeri bulana kadar devam edecek.

En İyi Durum: Hedef Değer, listenin orta konumunda

En Kötü Durum: Hedef Değer, listenin ilk veya son konumunda

Ne zaman kullanılmalı:

• Liste sıralandığında
• Liste büyük olduğunda

Derinlik Öncelikli Arama (Depth-first search)

Derinlik Öncelikli Arama (DFS), ağaç veya grafik veri yapılarında gezinmek veya arama yapmak için bir algoritmadır. Algoritma, kök düğümde başlar (bir grafik durumunda kök düğüm olarak bazı gelişigüzel düğümleri seçer) ve geri izleme öncesinde her dal boyunca mümkün olduğunca uzağa araştırma yapar.

DFS’de grafiğin, ağacın veya veri yapısının kökünü seçeriz ve sırayla her dalı keşfederiz. Bir dal seçildiğinde, farklı bir dala geçmeden önce tüm alt dallarını araştırır.

En İyi Durum: Hedef Değer, ağacın kök konumundadır

En Kötü Durum: Hedef Değer, sipariş edilen son şubenin bir alt dalının ucundadır

Ne zaman kullanılmalı:

• Ağaç çok geniş olduğunda
• Hedef değer ağacın derinliklerinde bulunduğunda

Sığ öncelikli arama (Breadth-first search)

Sığ öncelikli arama (BFS), ağaç veya grafik veri yapılarında gezinmek veya arama yapmak için bir algoritmadır. Ağaç kökünde (veya bir grafiğin rastgele bir düğümünde, bazen bir ‘arama anahtarı’ olarak anılır) başlar ve bir sonraki derinlik seviyesindeki düğümlere geçmeden önce mevcut derinlikteki tüm komşu düğümleri araştırır.

BSF’de, DFS’de olduğu gibi, grafiğin, ağacın veya veri yapısının kök düğümünü seçeriz. Düğümden sonra, tüm bitişik düğümüne ve ardından dala bitişik olan tüm düğüm olan bir sonraki seviyeye geçiyoruz.

En İyi Durum: Hedef Değer, ağacın kök konumundadır

En Kötü Durum: Hedef Değer, ağacın en uzun dalının ucundadır

Ne zaman kullanılmalı:

• Hedef değer ağacın kökünden uzak olmadığında
• Ağaç çok derin olduğunda ve hedef değer kökte olduğunda.

Kaynak: Suraj Vishwakarma – Algorithms Every Programmer Should Know: Part 1 (Searching Algorithm)