Binary Search (İkili Arama) verilmiş sıralı bir dizinde istenilen değeri arama işlemine denir. Programlama dünyasında en bilindik arama algoritmalarından biridir. Bir diğer bilindik arama algoritması ise Linear Search olarak bilinen doğrusal aramadır.
Linear Search genelde her programcının ilk kodlamaya başladığı zamanlarda kullanığı arama metodudur. Aradığınız elemanı bulmak için sırayla dizinin tüm elemanlarına bakarsınız ta ki aranan eleman bulunana kadar. Binary Search’te ise olay biraz farklı işler. Divide and Conquer (Parçala ve Fethet) yaklaşımı ile çalışan Binary Search’te dizinin tüm elemanlarını gezmenize gerek yoktur. Gelin yazının devamına kodlayarak devam edelim.
Linear Search
En bilindik 2 arama algoritmasının Linear ve Binary Search olduğundan bahsetmiştik. Linear Search ya da Sequential Search algoritmasında klasik bir şekilde dizinimizi bir for döngüsüne sokarız. Algoritma dizinin ilk elemanından başlar ve dizinin sonuna kadar tüm elemanlara teker teker bakar. Eğer baktığı eleman bizim aradığımız değere eşit ise bize o elemanın indeksini döndürür.
arr = [1,3,5,7,12,55,77,82,100]“arr” adında 9 elemana sahip bir dizin oluşturalım. Bu dizinde 12’yi aramak istediğimizi varsayalım. Bunun için kolayca oluşturulabilecek bir for döngüsü oluşturuyorum.
Yukarıdaki kod parçasındaki gibi algoritmamız en başta dizinin ilk elemanıyla, aranan değerimizi karşılaştıracak. Eğer baktığımız eleman aradığımız değer ise bize o elemanın indeksini yazdıracak. Bu işlemi bulana kadar yapacak ve söyle bir çıktı verecek.
Aranan değerin indeksi: 4Bir algoritmanın verimli olup olmadığını belirlemek için Büyük-O-Notasyonu kullanılır. Algoritmanın çalışma hızı donanım gibi dış faktörler nedeniyle farklılık gösterebileceğinden dolayı algoritmanın hızını belirlemek için saniyeleri kullanmak yerine gerçekleştirdiği işlem sayısını kullanırız.
Linear Search’te algoritmamız n indeksindeki bir elemanı bulmak için tam n kere karşılaştırma yapacağından Büyük-O-notasyonu O(n) olarak gösterilir.
Binary Search
Asıl konumuza şimdi gelebiliriz. Elinizdeki dizinin bir milyon tane elemana sahip olduğunu düşünün. Bir milyon kere karşılaştırma mı yapacaksınız? Yapabilirsiniz ama bu sisteminizi oldukça zorlayacaktır. Onun yerine karışıklığı daha düşük olan Binary Search’ü kullanabilirsiniz. Binary Search “Parçala ve Fethet” yaklaşımı ile birlikte verilen sıralı bir listeyi ortasından bölerek aradığı elemanı bulmaya çalışır. İlk olarak aradığı değeri, verilen dizindeki ortadaki elemanla karşılaştırır. Eğer eşitse direk ortadaki elemanın çıktısını bize verir. Eşit çıkmaz ise, eğer değer ortadaki elemandan büyükse aynı işlemi sağdaki parçayla yapar. Küçükse soldaki parçayla. Aradığı elemanı bulana kadar buna devam eder. Yukarıda oluşturduğumuz “arr” değişkeninden devam edelim ve yine 12’yi arayalım.
Yukarıda gözüktüğü gibi binarySearch() adında recursive(yinelemeli) bir fonksiyon yarattık. Bu fonksiyon parametre olarak arr: değeri arayacağımız dizin, value: aradığımız değer, low ve high: dizini her seferinde böleceğimizden bu oluşturacağımız mini dizinlerin ana dizindeki indeksleri.
Algoritmamız 4 aşamadan oluşmakta:
- Aranan değeri ortadaki elemanla karşılaştır
- Eğer eşit ise ortadaki elemanın indeksini döndür
- Eğer değer ortadaki elemana eşit değil ve ondan büyükse aynı algoritmayı yinelemeli biçimde dizinin ortadaki elemandan son elemanına kadar olan kısım ile yap.
- Eğer değer ortadaki elemana eşit değil ve ondan küçükse aynı algoritmayı yinelemeli biçimde dizinin en baştaki elemanından ortadaki elemanına kadar olan kısım ile yap.
Binary Search’te her seferinde dizimizin aralığını yarıya indirdiğimizden dolayı öteki yarısına bakmadan aramaya devam ediyoruz. Bu nedenle Binary Search’in karmaşıklığı O(log n) oluyor.
Binary Search ve Linear Search’ün ne kadar farklı çalıştığını, hız olarak ne kadar farklı olduklarını aşağıdaki örnekten anlayabilirsiniz.
