Search Algorithms: Verinin İçinde Yol Bulma Sanatı

Arama Problemi Nedir?

Arama problemi, belirli bir veri yapısı içerisinde hedef bir değeri bulma sürecidir.

Bu veri bir dizi (array), ağaç (tree), graf (graph) ya da hash tablosu olabilir.

Ancak veri yapısı ne olursa olsun, algoritmanın temel hedefi değişmez: en hızlı, en az maliyetle ve en doğru şekilde sonuca ulaşmak.

Temel Soru: "Bu veri içinde aradığım şey nerede?"

Bu soru basit görünse de, veri boyutu büyüdükçe çözümü kritik bir mühendislik problemine dönüşür.

Naif Yaklaşım ve Sınırları

En basit arama yöntemi, tüm veriyi baştan sona kontrol eden Linear Search yaklaşımıdır.

Bu yöntem küçük veri kümelerinde yeterli olsa da, veri boyutu arttıkça doğrusal zaman maliyeti (O(n)) ciddi bir performans sorununa dönüşür.

Örneğin milyonlarca kayıt içeren bir veri setinde, hedef elemanın en sonda olması durumunda, algoritma tüm veri üzerinden geçmek zorundadır.

Algoritmik Optimizasyon Mantığı Arama algoritmalarının gücü, verinin yapısal özelliklerini kullanarak arama alanını küçültmesinden gelir.

Örneğin: Sıralı bir veri üzerinde çalışan Binary Search, her adımda arama alanını ikiye bölerek problemi logaritmik zamana indirir.

Bu yaklaşım, brute-force yerine akıllı eliminasyon prensibine dayanır.

Veri Yapısı ile Algoritma İlişkisi

Arama performansı, yalnızca algoritmaya değil, aynı zamanda kullanılan veri yapısına da bağlıdır.

Örneğin:

• Array → sıralıysa Binary Search uygulanabilir
• Tree → hiyerarşik arama (BST, AVL)
• Graph → BFS / DFS ile keşif
• Hash Table → doğrudan erişim (O(1))

Yanlış veri yapısı seçimi, en iyi algoritmayı bile verimsiz hale getirebilir.

Gerçek Dünya ve Sistem Mimarisi

Arama algoritmaları, modern sistemlerin kalbinde yer alır.

Bir arama motoru, milyarlarca sayfa arasında sonuç döndürürken; bir veritabanı sorgusu, milyonlarca kayıt içinde filtreleme yaparken aynı temel prensipleri kullanır.

Bu sistemlerde amaç sadece doğru sonucu bulmak değil, aynı zamanda bunu milisaniyeler içinde gerçekleştirmektir.

Bu nedenle arama algoritmaları, sadece teorik değil; yüksek performanslı sistemlerin temel yapı taşıdır.

Arama Stratejilerinin Sınıflandırılması ve Temel Strateji Türleri

Arama algoritmaları, yalnızca bir hedefi bulmakla kalmaz; aynı zamanda bu hedefe nasıl yaklaşılacağını da belirler.

Bu nedenle arama problemleri, kullanılan yaklaşım modeline göre farklı stratejik kategorilere ayrılır.

Arama algoritmaları, yalnızca hedefi bulmakla değil; bu hedefe hangi yöntemle ulaşılacağını belirlemekle ilgilenir.

Bu nedenle arama problemleri, çözüm yaklaşımına göre farklı stratejilere ayrılır ve her biri farklı veri yapıları ve kullanım senaryoları için optimize edilmiştir.

• Doğrusal Tarama (Linear Scan): Verinin tamamını baştan sona sırayla gezerek hedefi bulur. Bu yaklaşım en basit ve en genel yöntemdir çünkü herhangi bir ön koşul gerektirmez.
  Ancak veri boyutu arttıkça her elemanın kontrol edilmesi gerektiğinden, zaman maliyeti doğrusal olarak büyür ve büyük veri setlerinde verimsiz hale gelir.
• Böl ve Fethet (Divide & Conquer): Arama alanını her adımda küçülterek problemi daha küçük parçalara böler.
  Binary Search bu yaklaşımın en klasik örneğidir; her adımda veri kümesini ikiye bölerek arama süresini dramatik şekilde azaltır.
  Ancak bu stratejinin çalışabilmesi için verinin önceden sıralı olması gerekir.
• Keşif Tabanlı (Traversal): Bu yaklaşım, lineer bir taramadan ziyade veri yapısının içinde yol izleyerek ilerleme mantığına dayanır.
  Özellikle graf ve ağaç yapılarında kullanılan BFS ve DFS, veriyi katman katman ya da derinlemesine keşfeder.
  Bu yöntemler, sadece arama değil aynı zamanda yapı analizi ve yol bulma problemlerinde de kullanılır.
• Hash Tabanlı Yaklaşım: Veriyi doğrudan adresleyerek arama sürecini neredeyse ortadan kaldırır.
  Bir hash fonksiyonu sayesinde anahtar, doğrudan bellekteki konumuna eşlenir ve bu sayede O(1) ortalama erişim sağlanır.
  Ancak bu hızın karşılığında, çakışma yönetimi ve ek bellek kullanımı gibi mühendislik problemleri ortaya çıkar.

Bu stratejiler arasındaki seçim, algoritmanın performansını belirleyen en kritik faktördür.

Doğru strateji, verinin yapısı ile uyumlu olduğunda minimum maliyetle maksimum verim sağlar.

Strateji Seçimi ve Algoritmik Karar

Doğru arama stratejisini seçmek, algoritmanın performansını doğrudan belirler.

Bu seçim rastgele değil; verinin yapısı, boyutu ve erişim şekline göre yapılmalıdır.

Yanlış strateji seçimi, teorik olarak doğru çalışan bir algoritmayı bile pratikte kullanılamaz hale getirebilir.

Veri Yapısına Göre Optimizasyon

Her veri yapısı, farklı bir arama yaklaşımını gerektirir.

• Sıralı veri: Binary Search kullanılarak arama alanı her adımda ikiye bölünür.
  Bu sayede işlem süresi logaritmik seviyeye düşer ve büyük veri setlerinde ciddi performans avantajı sağlar.
• Graf yapıları: BFS / DFS algoritmaları ile veri, bağlantılar üzerinden sistematik olarak keşfedilir.
  Bu yaklaşım, yalnızca değer bulmayı değil, yapı içinde gezinmeyi ve yol bulmayı mümkün kılar.
• Büyük veri setleri: Hashing kullanılarak veriye doğrudan erişim sağlanır.
  Ortalama durumda O(1) zaman karmaşıklığı ile arama yapılabilir ve bu, yüksek performanslı sistemlerin temelini oluşturur.

Bu eşleşme, algoritma tasarımında veri + strateji uyumu olarak adlandırılır ve performansın temel belirleyicisidir.

Algoritmalara Geçiş

Şimdiye kadar arama problemini farklı açılardan ele aldık: verinin yapısını, stratejileri ve performans farklarını analiz ettik.

Ancak algoritmalar yalnızca teorik tanımlardan ibaret değildir; onlar, bu soyut fikirlerin adım adım uygulanabilir hale getirilmiş formudur.

Bu noktadan sonra odak noktamız değişiyor: "hangi algoritma nedir?" sorusundan, "bir algoritma nasıl düşünülür ve nasıl inşa edilir?" sorusuna geçiyoruz.

Çünkü gerçek yazılım geliştirme sürecinde önemli olan, hazır bir çözümü ezberlemek değil; problemi parçalayıp doğru çözüm modelini kurabilmektir.

Algoritmik Düşünme Modeli

Her algoritma aslında şu üç temel soruya verilen sistematik bir cevaptır:

• Veriyi nasıl okuyorum?
  Veriye erişim biçimi, algoritmanın temelini belirler. Lineer mi ilerliyorum, yoksa belirli noktalara mı sıçrıyorum?
  Bu seçim, arama hızını doğrudan etkiler.
• Karşılaştırmayı nasıl yapıyorum?
  Her adımda yapılan karşılaştırma, algoritmanın karar mekanizmasını oluşturur.
  Basit eşitlik kontrolü mü, yoksa aralığı daraltan bir strateji mi kullanıyorum?
  Bu yaklaşım, algoritmanın verimliliğini belirler.
• Ne zaman duruyorum?
  Algoritmanın durma koşulu, hem doğruluğu hem de performansı etkiler.
  Hedef bulunduğunda mı duruyorum, yoksa arama alanı tükendiğinde mi?
  Doğru tanımlanmış bir bitiş koşulu, gereksiz işlemleri engeller.

Bu üç adımın doğru tasarlanması, algoritmanın hem doğruluğunu hem de performansını belirler.

Zihinsel Model ve Öğrenme Stratejisi

Algoritmaları öğrenmenin en doğru yolu, onları sadece kod olarak görmek değil; bir düşünme modeli olarak anlamaktır.

Bu yüzden her algoritmayı incelerken, sadece "ne yapıyor?" değil, "neden bu şekilde çalışıyor?" sorusunu da sormamız gerekir.

Başlangıç Noktası: Bu yolculuğa, en temel ve en sezgisel arama modeli ile başlıyoruz: Linear Search.

Basit yapısına rağmen bu algoritma, arama probleminin özünü anlamak için temel referans noktası görevini görür.

Çünkü daha karmaşık tüm arama algoritmaları, aslında bu temel yaklaşımın optimize edilmiş versiyonlarıdır.

Temel Tanım ve Mantıksal Yapı

Linear Search, bir veri yapısı içerisinde hedef bir değeri bulmak için elemanları baştan sona sırayla kontrol eden en temel arama algoritmasıdır.

Bu yaklaşımda herhangi bir ön bilgiye ihtiyaç yoktur; veri sıralı olmak zorunda değildir ve algoritma, her elemanı tek tek inceleyerek sonuca ulaşır.

Bu nedenle Linear Search, algoritmik dünyada en genel ve en garantili çalışan yöntem olarak kabul edilir.

Algoritmanın Çalışma Prensibi

Algoritma, veri yapısının ilk elemanından başlar ve her adımda mevcut elemanı hedef değer ile karşılaştırır.

Eğer eşleşme bulunursa arama sonlandırılır; aksi durumda algoritma bir sonraki elemana geçer.

Bu süreç, hedef bulunana kadar veya veri sonuna ulaşılana kadar devam eder.

Zaman Karmaşıklığı Analizi Linear Search algoritmasının zaman karmaşıklığı O(n)'dir.

En iyi durumda hedef ilk elemanda bulunur (O(1)), en kötü durumda ise tüm veri taranır.

Bu da algoritmanın performansının doğrudan veri boyutuna bağlı olduğu anlamına gelir.

Avantajlar ve Sınırlamalar Linear Search'in en büyük avantajı, her koşulda çalışabilmesidir.

Ancak bu esneklik, performans maliyeti ile birlikte gelir. Büyük veri setlerinde algoritma oldukça yavaş kalır.

Bu nedenle Linear Search, genellikle küçük veri setlerinde veya veri sıralı olmadığında tercih edilir.

Gerçek Dünya Perspektifi Linear Search, basit görünmesine rağmen birçok sistemde hâlâ kullanılmaktadır.

Örneğin: Küçük veri listelerinde, filtreleme işlemlerinde veya sıralı olmayan veri kümelerinde en pratik çözüm olarak tercih edilir.

Ayrıca bu algoritma, daha gelişmiş arama yöntemlerini anlamak için referans model görevi görür.

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // bulundu
    }
  }
  return -1; // bulunamadı
}

// Örnek kullanım
const data = [5, 8, 12, 20, 3];
const result = linearSearch(data, 12);

console.log(result); // 2

Temel Fikir ve Paradigma

Binary Search, arama problemini çözmek için veriyi doğrudan taramak yerine arama alanını sürekli küçülten bir yaklaşıma dayanır.

Bu algoritma, Divide & Conquer paradigmasını kullanarak, her adımda problemi ikiye böler ve yalnızca gerekli olan yarı üzerinde çalışır.

Linear Search ile Temel Fark Linear Search tüm veri üzerinde ilerlerken, Binary Search her adımda verinin yarısını doğrudan eler.

Bu fark, algoritmanın performansını dramatik şekilde değiştirir:

• Linear Search → O(n)
  Veri seti büyüdükçe, arama süresi doğrusal olarak artar.
  En kötü durumda tüm elemanlar kontrol edilir, bu da büyük veri setlerinde maliyeti yükseltir.
• Binary Search → O(log n)
  Her adımda arama alanı ikiye bölünür, bu nedenle işlem sayısı çok daha yavaş artar.
  Bu yaklaşım, büyük veri setlerinde ciddi performans avantajı sağlar.

Bu da büyük veri setlerinde Binary Search’ün kat kat daha hızlı olduğu anlamına gelir.

Çalışma Prensibi

Algoritma, veri setinin ortasındaki elemanı seçerek başlar.

Seçilen orta değer ile hedef karşılaştırılır:

• Hedef değer orta elemandan küçükse → arama alanı sol yarıya daraltılır.
  Bu sayede sağ taraftaki tüm elemanlar tek adımda elenir.
• Hedef değer orta elemandan büyükse → arama sağ yarıda devam eder.
  Sol taraftaki tüm olasılıklar göz ardı edilerek arama alanı küçültülür.
• Hedef değer orta elemana eşitse → arama başarıyla tamamlanır.
  Bu durumda algoritma, en kısa yoldan sonuca ulaşmış olur.

Bu işlem, arama alanı kalmayana kadar tekrar eder.

Kritik Ön Koşul Binary Search’ün çalışabilmesi için veri setinin sıralı olması zorunludur.

Sıralanmamış bir veri üzerinde bu algoritma çalışmaz; çünkü algoritmanın karar mekanizması, verinin düzenine güvenerek hareket eder.

Zaman Karmaşıklığı ve Ölçeklenebilirlik

Binary Search’te her adımda veri yarıya düştüğü için, işlem sayısı logaritmik olarak artar.

Örneğin:

Binary Search’te veri boyutu büyüse bile, arama adım sayısı çok yavaş artar.

• 1.000 eleman → yaklaşık 10 adım
  Çünkü her adımda veri yarıya indirilir.
• 1.000.000 eleman → yaklaşık 20 adım
  Veri 1000 kat artsa bile, işlem sayısı sadece birkaç adım artar.

Bu durum, logaritmik büyümenin gücünü açıkça gösterir: veri büyür, ancak işlem maliyeti neredeyse sabit kalır.

Bu özellik, Binary Search’ü büyük veri sistemleri için vazgeçilmez hale getirir.

Algoritmik Kazanım Binary Search, sadece hızlı bir arama yöntemi değildir; aynı zamanda algoritmik düşünmede "eliminasyon stratejisi" kavramını öğretir.

Yani problemi çözmek için her şeyi denemek yerine, gereksiz olanı sistematik şekilde dışlamak daha güçlü bir yaklaşımdır.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid;
    }

    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}
// kullanım
const data = [2, 4, 6, 8, 10, 12, 14];
console.log(binarySearch(data, 10)); // 4

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) return -1;

  let mid = Math.floor((left + right) / 2);

  if (arr[mid] === target) return mid;

  if (target < arr[mid]) {
    return binarySearchRecursive(arr, target, left, mid - 1);
  } else {
    return binarySearchRecursive(arr, target, mid + 1, right);
  }
}

Edge Case ve Kritik Durumlar

Binary Search, belirli varsayımlar üzerine kurulu bir algoritmadır ve bu varsayımlar bozulduğunda sonuçlar ciddi şekilde etkilenebilir.

Bu nedenle algoritmanın doğru çalışması için sınır durumlarını (edge cases) iyi anlamak kritik öneme sahiptir.

• Boş dizi: Veri kümesi boşsa arama yapılacak hiçbir eleman yoktur, bu nedenle algoritma doğrudan başarısız sonuç döndürür.
  Bu durum, algoritma başlamadan önce giriş kontrolü yapılmasının önemini gösterir.
• Tek eleman: Arama aralığı yalnızca bir index’e düşer ve mid = 0 olur.
  Bu senaryoda algoritma, minimum işlemle sonucu belirler.
• Bulunamayan değer: Arama alanı her adımda daraltılır ve sonunda left > right durumu oluşur.
  Bu nokta, tüm olası konumların tüketildiğini ve hedefin veri içinde bulunmadığını ifade eder.
• Duplicate (tekrar eden değerler): Aynı değerin birden fazla bulunduğu durumlarda, algoritma herhangi bir uygun index’i döndürebilir.
  Belirli bir konum (örneğin ilk veya son index) isteniyorsa, ek arama stratejileri gerekir.
• Sıralı olmayan veri: Binary Search’ün temel varsayımı sıralı veridir.
  Bu şart sağlanmazsa, karşılaştırma yönü anlamsız hale gelir ve algoritma güvenilirliğini kaybeder.

Yaygın Hatalar ve Tuzaklar

Binary Search, basit görünmesine rağmen pratikte en çok hata yapılan algoritmalardan biridir.

Bu hatalar genellikle küçük detaylardan kaynaklanır, ancak algoritmanın tamamen yanlış çalışmasına neden olabilir.

Gerçek Dünya Senaryosu

Büyük bir kullanıcı veri tabanında belirli bir ID’yi bulmak istediğimizi düşünelim.

Linear Search bu veri setini baştan sona tararken, Binary Search her adımda veri setinin yarısını eleyerek ilerler.

Bu fark, milyonlarca kayıt içeren sistemlerde milisaniyeler ile saniyeler arasındaki farkı oluşturabilir.

Bu nedenle Binary Search, özellikle büyük ölçekli veri işleyen sistemlerde performans açısından kritik bir rol oynar.

Temel Fikir ve Yaklaşım

Jump Search, Linear Search ile Binary Search arasında konumlanan hibrit bir arama algoritmasıdır.

Bu algoritma, veriyi tek tek taramak yerine belirli adımlar halinde atlayarak ilerler ve hedefin bulunduğu aralığı hızlıca daraltır.

Linear ve Binary ile Farkı

Jump Search, iki algoritmanın yaklaşımını dengeler:

• Linear Search → her elemanı kontrol eder (yavaş ama garantili)
• Binary Search → aralığı sürekli böler (çok hızlı ama katı koşullu)
• Jump Search → aralıkları blok halinde geçer, sonra lokal arama yapar

Bu yaklaşım, kontrollü hızlanma sağlar.

Çalışma Prensibi

Algoritma, veri seti üzerinde belirli bir adım büyüklüğü ile ilerler.

Genellikle bu adım büyüklüğü √n (karekök n) olarak seçilir.

• 1. Adım: Blok blok ilerle (0 → √n → 2√n ...)
• 2. Hedef aralığı bul
• 3. O blok içinde Linear Search yap

Böylece algoritma, tüm veri yerine sadece belirli bir kısmı detaylı inceler.

Zaman Karmaşıklığı

Jump Search’ün ortalama zaman karmaşıklığı: O(√n)

Bu, Linear Search’ten hızlı, ancak Binary Search’ten daha yavaştır.

Ancak bazı sistemlerde daha az bellek erişimi yaptığı için tercih edilebilir.

Kullanım Senaryosu

Jump Search, özellikle sıralı veri üzerinde çalışır ve rastgele erişimin pahalı olduğu durumlarda avantaj sağlar.

Örneğin:

• Disk tabanlı veri okuma
• Cache optimizasyonu gereken sistemler
• Sequential erişim ağırlıklı veri yapıları

Algoritmik Perspektif

Jump Search, algoritmik düşünmede önemli bir kavramı öğretir: "her şeyi kontrol etmek yerine akıllı sıçramalar yapmak".

Bu yaklaşım, veri üzerinde doğrudan gezinmek yerine önce alanı daraltıp sonra detaylı inceleme stratejisine dayanır.

Blok Mantığı ve Kritik Davranışlar

Jump Search, diğer arama algoritmalarından farklı olarak veriyi tek tek incelemek yerine bloklar halinde atlayarak ilerler.

Bu yaklaşım performansı artırsa da, algoritmanın doğruluğu tamamen doğru blok seçimi ve sınır kontrolüne bağlıdır.

• Blok kaçırma riski: Eğer atlama aralığı yanlış yönetilirse, hedef değerin bulunduğu blok tamamen atlanabilir.
• Son blok durumu: Dizinin sonuna yaklaşıldığında, adım büyüklüğü veri sınırını aşabilir ve bu durum dikkatli kontrol edilmezse hataya yol açar.
• Küçük veri setleri: Veri boyutu düşükse Jump Search, Linear Search’ten daha verimsiz hale gelebilir.

Optimizasyon Tuzakları

Jump Search’ün performansı, kullanılan adım büyüklüğüne doğrudan bağlıdır.

Genellikle √n optimal kabul edilir, ancak bu değer yanlış seçildiğinde algoritma ya Linear Search’e yaklaşır ya da gereksiz atlamalar yaparak verimsiz hale gelir.

• ❌ Çok küçük step: Algoritma neredeyse Linear Search gibi davranır.
• ❌ Çok büyük step: Gereksiz geniş atlamalar yapılır, ardından uzun bir lokal tarama gerekir.
• ❌ Blok içi arama ihmal edilirse: Hedef değer kaçırılır ve yanlış sonuç elde edilir.

Algoritmik İçgörü

Jump Search, algoritma tasarımında önemli bir dengeyi temsil eder: hız ve kontrol arasında seçim yapmak.

Bu algoritma bize şunu öğretir: her zaman en hızlı yöntem değil, en dengeli yöntem en doğru çözüm olabilir .

Özellikle sistem tasarımında, gereksiz hesaplamaları azaltırken doğruluğu korumak, bu tür hibrit algoritmaların temel amacıdır.

function jumpSearch(arr, target) {
  const n = arr.length;
  // optimal adım büyüklüğü
  const step = Math.floor(Math.sqrt(n));

  let prev = 0;
  let current = step;

  // 1. BLOK ATLAMA
  while (arr[Math.min(current, n) - 1] < target) {
    prev = current;
    current += step;

    if (prev >= n) {
      return -1; // bulunamadı
    }
  }

  // 2. BLOK İÇİNDE LINEAR SEARCH
  for (let i = prev; i < Math.min(current, n); i++) {
    if (arr[i] === target) {
      return i;
    }
  }

  return -1;
}
// kullanım
const data = [2, 4, 6, 8, 10, 12, 14, 16, 18];
console.log(jumpSearch(data, 12)); // 5

Temel Fikir ve Paradigma

Interpolation Search, arama sürecinde yalnızca ortayı kontrol etmek yerine, verinin dağılımını kullanarak tahmin yapan bir algoritmadır.

Bu yaklaşım, Binary Search’ten farklı olarak sabit bir bölme yerine verinin değer aralığına göre dinamik konum belirler.

Binary Search ile Farkı

Binary Search her zaman ortadan başlar, ancak Interpolation Search, hedef değerin nerede olabileceğini tahmin ederek doğrudan o noktaya gider.

• Binary → ortayı kontrol eder
• Interpolation → olası konumu hesaplar

Bu fark, özellikle verinin eşit dağıldığı durumlarda algoritmayı çok daha hızlı hale getirir.

Tahmin Mekanizması

Algoritma, hedefin konumunu şu mantıkla hesaplar:

Eğer değerler düzgün dağılmışsa, hedefin konumu da bu dağılıma göre tahmin edilebilir.

Bu nedenle algoritma, değer aralığına göre konum tahmini yapar ve doğrudan o noktaya atlar.

Zaman Karmaşıklığı

Ortalama durumda: O(log log n)

Bu, Binary Search’ten bile daha hızlıdır.

Ancak veri dağılımı düzensizse, algoritma O(n)’e kadar düşebilir.

Veri Dağılımının Önemi

Interpolation Search’ün performansı, doğrudan verinin nasıl dağıldığına bağlıdır.

• Eşit dağılım → maksimum performans
• Düzensiz dağılım → performans düşüşü

Bu nedenle bu algoritma, veri yapısını anlayabilen akıllı algoritmalar kategorisine girer.

Algoritmik İçgörü

Interpolation Search, algoritma tasarımında ileri bir konsepti temsil eder: veriye uyum sağlayan algoritmalar.

Bu yaklaşımda algoritma, veriyi sadece taramaz; veriyi analiz eder ve davranışını buna göre değiştirir.

Bu da onu, modern veri işleme sistemlerinde önemli bir kavram haline getirir.

Tahmin Formülü ve Matematiksel Model

Interpolation Search’ün temel farkı, arama konumunu sabit seçmek yerine matematiksel olarak tahmin etmesidir.

Bu tahmin aşağıdaki formül ile yapılır:

pos = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left])

Bu formül, hedef değerin veri aralığında nerede olması gerektiğini orantısal olarak hesaplar.

• left: başlangıç index
• right: bitiş index
• arr[left], arr[right]: değer aralığı

Eğer veri eşit dağılıyorsa, bu tahmin oldukça isabetli olur ve arama hızlanır.

Dağılım ve Tahmin Riskleri

Interpolation Search’ün doğruluğu, tamamen veri dağılımına bağlıdır.

• Düzensiz veri: Tahmin hatalı olur ve algoritma Linear Search performansına düşer.
• Tekrarlı değerler: (arr[left] == arr[right]) durumunda bölme hatası oluşabilir.
• Hedef aralık dışında: target < arr[left] veya target> arr[right] → arama gereksiz yere yapılmaz.
• Yoğunluk farkı: Veri belirli bölgelerde sıkışmışsa, tahmin sürekli yanlış noktaya gider.

Tahmin Hataları ve Algoritmik Tuzaklar

• ❌ Sıralama kontrol edilmemesi: Algoritma tamamen yanlış sonuç verir.
• ❌ Bölme sıfır hatası: arr[left] == arr[right] kontrol edilmezse crash olur.
• ❌ pos sınır dışı çıkması: Tahmin yanlışsa index overflow olabilir.
• ❌ Dağılım varsayımı: Veri eşit dağılmamışsa performans ciddi düşer.

function interpolationSearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (
    left <= right &&
    target >= arr[left] &&
    target <= arr[right]
  ) {

    // bölme hatasını önlemek için kontrol
    if (arr[left] === arr[right]) {
      if (arr[left] === target) return left;
      return -1;
    }

    let pos = left + Math.floor(
      ((target - arr[left]) * (right - left)) /
      (arr[right] - arr[left])
    );

    if (arr[pos] === target) {
      return pos;
    }

    if (arr[pos] < target) {
      left = pos + 1;
    } else {
      right = pos - 1;
    }
  }
  return -1;
}
// kullanım
const data = [10, 20, 30, 40, 50, 60, 70];
console.log(interpolationSearch(data, 50)); // 4

Yeni Paradigma: Veri Değil Yapı

Önceki algoritmalarda arama, lineer bir veri üzerinde yapılıyordu. Ancak gerçek dünyada veriler çoğu zaman bu şekilde düzenli değildir.

Sosyal ağlar, haritalar, bağlantı sistemleri gibi yapılar, node ve edge’lerden oluşan graph yapılarıdır.

Bu tür yapılarda arama yapmak, yalnızca "değer bulmak" değil, yol bulmak ve yapı keşfetmek anlamına gelir.

Traversal (Gezinme) Mantığı

Graph arama algoritmaları, veriyi doğrudan index ile erişmek yerine, bağlantılar üzerinden ilerler.

Bu süreçte amaç:

• Tüm node’ları gezmek
• Belirli bir node’a ulaşmak
• En kısa yolu bulmak

İki Temel Yaklaşım

Graph traversal için iki temel strateji vardır:

• BFS (Breadth-First Search) → graph üzerinde katman katman ilerleyerek en yakın düğümleri önce keşfeder.
  Mesafe ve erişim önceliği odaklıdır.
• DFS (Depth-First Search) → bir yolu seçip olabildiğince derine iner, çıkmaza ulaştığında geri dönerek alternatif yolları dener.
  Yol keşfi ve olasılık analizi odaklıdır.

Bu iki yaklaşım, aynı problemi farklı bakış açılarıyla çözer.

// Graph adjacency list (komşuluk listesi)
const graph = {
  A: ["B", "C"],
  B: ["D", "E"],
  C: ["F"],
  D: [],
  E: ["F"],
  F: []
};

// basit traversal (DFS mantığıyla)
function traverseGraph(graph, start) {
  const visited = new Set();

  function dfs(node) {
    if (visited.has(node)) return;

    console.log(node);
    visited.add(node);

    for (let neighbor of graph[node]) {
      dfs(neighbor);
    }
  }

  dfs(start);
}
// kullanım
traverseGraph(graph, "A");

Temel Mantık

BFS (Breadth-First Search), graph üzerinde keşif yaparken genişlik öncelikli ilerleyen bir algoritmadır.

Bu yaklaşımda algoritma, bir düğümden başlar ve önce o düğümün tüm komşularını ziyaret eder, ardından bir sonraki seviyedeki düğümlere geçer.

Yani keşif süreci, mesafe bazlı katmanlar halinde ilerler.

Veri Yapısı ve Çalışma Modeli

BFS algoritması, düğümleri sırayla işlemek için Queue (kuyruk) veri yapısını kullanır.

Kuyruk yapısı, ilk giren ilk çıkar (FIFO) mantığı ile çalışır ve bu sayede düğümler doğru sırayla işlenir.

Bu sıralama, BFS’in neden katman katman ilerlediğini açıklar: önce eklenen düğümler önce işlenir.

Algoritmik Özellik

BFS’in en önemli özelliği, bir düğüme ulaşırken en kısa yolu garanti etmesidir (unweighted graph için).

Çünkü algoritma, daha uzak düğümlere geçmeden önce tüm yakın düğümleri ziyaret eder.

Kullanım Alanları

BFS, özellikle düğümler arasındaki mesafe ve erişim sırası önemli olduğunda tercih edilen bir algoritmadır.

Katman katman ilerleyen yapısı sayesinde, en yakın düğümler her zaman önce işlenir ve bu da algoritmayı mesafe tabanlı problemlerde güçlü hale getirir.

• En kısa yol bulma: Ağırlıksız graph’larda iki düğüm arasındaki minimum adım sayısını garanti eder.
  Çünkü algoritma, daha uzak düğümlere geçmeden önce tüm yakın düğümleri ziyaret eder.
• Sosyal ağ analizleri: Bir kullanıcının diğer kullanıcılarla olan bağlantı uzaklığı (degree of separation) hesaplanabilir.
  Örneğin: "Bu kişi bana kaç bağlantı uzaklıkta?"
• Seviye bazlı sistemler: BFS, yapıyı katmanlara ayırarak işler.
  Bu nedenle oyun level sistemleri, organizasyon hiyerarşileri ve ağaç yapıları için idealdir.
• Broadcast / yayılma sistemleri: Bilginin tüm ağa en kısa sürede yayılması gereken durumlarda kullanılır.
  (örnek: ağ protokolleri, mesaj yayılımı)

BFS, özellikle "en yakın olanı önce bul" mantığı gerektiren problemlerde en doğru seçimdir.

BFS, özellikle mesafe ve erişim önceliği önemli olduğunda tercih edilen bir algoritmadır.

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];

  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift(); // FIFO

    console.log(node);

    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}
// örnek graph
const graph = {
  A: ["B", "C"],
  B: ["D", "E"],
  C: ["F"],
  D: [],
  E: ["F"],
  F: []
};
// kullanım
bfs(graph, "A");

Temel Mantık

DFS (Depth-First Search), graph üzerinde keşif yaparken derinlik öncelikli ilerleyen bir algoritmadır.

Algoritma, bir düğümden başlar ve mümkün olan ilk yolu seçerek olabildiğince derine iner.

Eğer ilerleyebileceği başka düğüm kalmazsa, bulunduğu noktadan geri dönerek alternatif yolları keşfetmeye devam eder.

Bu süreç, ilerle → çıkmaz → geri dön → yeni yol dene şeklinde döngüsel olarak devam eder.

Veri Yapısı ve Çalışma Modeli

DFS algoritması, ziyaret edilen düğümleri yönetmek için Stack veri yapısını kullanır.

Stack yapısı, son giren ilk çıkar (LIFO) mantığı ile çalışır ve bu sayede algoritma, en son keşfedilen yolu derinlemesine takip eder.

Recursive (özyinelemeli) kullanımda ise bu stack yapısı sistem tarafından otomatik olarak yönetilir.

Algoritmik Özellik

DFS’in en belirgin özelliği, tüm olası yolları keşfetmeye uygun olmasıdır.

Bu nedenle algoritma, çözümün tek bir yol yerine birden fazla ihtimale bağlı olduğu problemlerde güçlüdür.

Kullanım Alanları

DFS, özellikle çözümün tek bir yol üzerinden değil, birden fazla olasılık üzerinden ilerlediği problemlerde güçlü bir yaklaşımdır.

Algoritmanın derinlemesine ilerleme ve geri dönme (backtracking) yapısı, onu keşif ve deneme tabanlı sistemlerde vazgeçilmez hale getirir.

• Backtracking problemleri: DFS, tüm olası çözüm yollarını sistematik olarak denemek için kullanılır.
  Her yol sonuna kadar denenir, ardından geri dönülür ve alternatif yollar keşfedilir.
• Labirent ve yol bulma: Algoritma, bir yolu sonuna kadar takip ederek çıkışa ulaşmaya çalışır.
  Eğer yol çıkmazsa, geri dönerek yeni bir yön dener.
• Cycle detection (döngü tespiti): DFS, graph içinde daha önce ziyaret edilen bir düğüme tekrar ulaşarak döngüleri tespit edebilir.
• Topological sorting: Bağımlılık ilişkisi olan sistemlerde, işlemlerin doğru sırada yapılmasını sağlamak için kullanılır.
• Connected components: Graph içinde birbirine bağlı alt yapıları keşfetmek için kullanılır.

DFS, özellikle tüm yolları keşfetmek veya bir çözüm yolunu derinlemesine analiz etmek gerektiğinde tercih edilir.

DFS, özellikle yol keşfi ve olasılık analizi gerektiren problemlerde tercih edilir.

function dfs(graph, node, visited = new Set()) {
  if (visited.has(node)) return;

  console.log(node);
  visited.add(node);

  for (let neighbor of graph[node]) {
    dfs(graph, neighbor, visited);
  }
}

// örnek graph
const graph = {
  A: ["B", "C"],
  B: ["D", "E"],
  C: ["F"],
  D: [],
  E: ["F"],
  F: []
};
// kullanım
dfs(graph, "A");

function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];

  while (stack.length > 0) {
    const node = stack.pop(); // LIFO

    if (!visited.has(node)) {
      console.log(node);
      visited.add(node);

      // ters sırayla eklemek traversal sırasını korur
      for (let i = graph[node].length - 1; i >= 0; i--) {
        stack.push(graph[node][i]);
      }
    }
  }
}

// kullanım
dfsIterative(graph, "A");

Hangi Durumda Hangisi?

BFS ve DFS aynı veri yapısı üzerinde çalışsa da, tamamen farklı problem türleri için optimize edilmiştir.

Bu nedenle doğru algoritmayı seçmek, yalnızca performansı değil, problemin doğru çözülmesini de belirler.

• En kısa yolu bulmak istiyorsan → BFS
  Çünkü BFS, katman katman ilerleyerek hedefe minimum adım sayısı ile ulaşmayı garanti eder.
• Tüm olası yolları keşfetmek istiyorsan → DFS
  DFS, her yolu sonuna kadar deneyerek tüm çözüm ihtimallerini ortaya çıkarır.
• Bellek sınırlıysa → DFS
  Çünkü DFS yalnızca tek bir yol üzerinde ilerler, BFS gibi tüm seviyeyi bellekte tutmaz.
• Hedefe en hızlı şekilde (yakınlık öncelikli) ulaşmak istiyorsan → BFS
  En yakın düğümler önce işlendiği için, çözüm genellikle daha erken bulunur.

Özetle: BFS mesafe odaklıdır, DFS ise keşif odaklıdır.