Search(Arama) Algoritmaları: Linear & Binary Search

Arama algoritmaları, bilgisayar bilimleri için önemli konulardan biridir. Arama algoritmaları adından da anlaşılacağı gibi, bir veri yapısı(data structure) üzerinde belirli bir verinin aranması için kullanılan algoritmalar bütünüdür. Bu veri yapısı bir liste, array ya da graph olabilir. Belirli durumlara özgü farklı arama algoritmaları geliştirilmiştir ve hepsinin birbirine göre farklı avantajları ve farklı çalışma süreleri vardır. Genel olarak bir liste ya da dizi üzerinde arama yapacaksanız iki temel kategori bulunmakta. Bunlardan biri Sequential(Sıralı/Ardışık) Search, diğeri ise Interval(Aralıklı) Search. Bunların altında da farklı algoritmalar geliştirilmiştir. Bunlardan en basit ve anlaşılır olanlardan ikisi de Linear Search ve Binary Search.

Sequential Search, veri yapımızda verilerin belli bir sıra ile tutulmadığı ve en kötü durumda arama için dizideki her bir veriyi ziyaret edeceğimiz arama çeşididir. Bunun en güzel örneği de Linear Search algoritmasıdır.

Interval Search ise sıralı veri yapısı üzerinde uygulanan algoritmalar için kullanılır. Bunun altında Binary Search, Jump Search, Exponential Search, Fibonacci Search gibi algoritmalar bulunur. Bunlar haricinde birçok farklı algoritma geliştirilmiştir. Hali hazırda bilindik bu algoritmaların da birçoğunun geliştirilmiş versiyonu bulunmaktadır. Biz bu yazıda konuya aşinalık kazandırmak için iki tane temel algoritmanın çalışma mantığına bakacağız.

Linear Search

Bu arama algoritması en basit ve çalışma zamanı olarak en kötü algoritmalardan biridir. Çünkü en kötü ihtimal ile veri yapımız üzerinde tüm elemanları gezmesi gerekir. Burada en kötü ihtimalden kastımız algoritmamızın zaman karmaşıklığı(time complexity). Bunun içinde bilgisayar bilimlerinde algoritmaların analizi için çeşitli notasyonlar(asymptotic notations) kullanılır. Bunlar Big O(Ο), Omega(Ω) ve Theta(θ) notasyonlarıdır.

Big O notasyonu en kötü durum(worst case) için, Omega en iyi durum(best case), Theta ise ortalama durum(average case) için kullanılır. Birazdan bu iki algoritmanın zaman karmaşıklıklarını inceleyeceğiz. Önce mantıklarına bakalım.

Linear Search, verilen veri seti üzerinde her bir eleman ile aranan değeri karşılaştırarak arar. Eğer aranan veri dizide bulunursa dizinin indeksini döner. Bulamazsa -1 gibi bir değer döner.

görsel kaynak: tutorialspoint.com

Bu algoritmanın zaman karmaşıklığı O(n)’dir. Burada n değeri inputu temsil ediyor. Uzunluğu “n” olan bir dizi için en kötü durumda “n” kez çalışacak demek oluyor.