Merhaba arkadaşlar,
Mobilhanem.com üzerinden anlattığımız/yayınladığımız Algoritma Eğitimleri serimize devam ediyoruz. Algoritma Eğitimlerinde Search ve Sort Algoritmalarından sonra Örnek Algoritma Soruları ve Çözümleri ile öğrendiğimiz Algoritmaları pekiştiriyoruz.
Bu yazı genel olarak Binary Search ile ilgili olacaktır eğer Binary Search algoritmasını bilmiyorsanız buradan öğrenebilirsiniz.
Neden Algoritma Soruları çözmeliyiz?
Algoritma soruları çözmek bir olaya ya da bir probleme farklı pencerelerden bakma şansı tanır ve böylelikle karşılaştığımız sorunlara karşı(teknik veya değil) yorum yapabilme kabiliyeti kazandırır.
Öncelikle basit bir arama algoritması yazarak ısınma turu yapalım.
Örnek 1:
Elimizde sayılardan oluşan bir liste olsun ve istediğimiz sayıları içinde arayalım. Eğer var ise ekrana “VAR” eğer aradığımız eleman listede yok ise “YOK” yazalım.
Girdiler:
Sayı Listesi ve Aranan Değer
Çıktı:
Eğer aranan sayı listede var ise “VAR” yok ise “YOK” yazısı.
Örnek Girdi 1:
{11, 8, 1, 4, 17, 21, 14, 30, 22} ve aranan değer 15
Örnek Çıktı 1:
YOK
Örnek Girdi 2:
{11, 8, 1, 4, 17, 21, 14, 30, 22} ve aranan değer 4
Örnek Çıktı 2:
VAR
Java Kodu
static void search(List<Integer> list, int value){
boolean flag = false;
for (int i=0; i<list.size(); i++){
if (list.get(i) == value){
flag = true;
break;
}else{
flag = false;
}
}
if (flag){
result = "VAR";
}else{
result = "YOK";
}
}
Buraya kadar basit bir arama algoritması çalıştırdık ve aranan değeri kontrol ettik.
Şimdi bir arama algoritması yardımı ile bunu gerçekleştirelim ve soruyu biraz değiştirerek aranan bir değer değil birden fazla değer olsun.
Örnek 2:
Örnek 1 den farklı olarak arama binary search ile yapılacak ve ek olarak aranan kısım tek bir değer değil bir liste (birden çok değer) olacak.
Girdiler:
Sayı Listesi ve Aranan Listesi
Çıktı:
Eğer aranan listedeki ilgili değer mevcut listede var ise “VAR” yok ise “YOK” yazısı.
Örnek Girdi 1:
{11, 8, 1, 4, 17, 21, 14, 30, 22} ve aranan liste {15, 4, 8, 21, 10, 7}
Örnek Çıktı 1:
YOK
VAR
VAR
VAR
YOK
YOK
Java Kodu
Collections.sort(integerList); // binary search algoritması kullanabilmek için elimizdeki mevcut değerleri sıraladık.
//birden fazla değer aradığımız için döngü ile kullandık.
for (int i=0; i<integerListTest.size(); i++){
binarySearch(integerList, integerListTest.get(i));
System.out.println(result);
}
static void binarySearch(List<Integer> list, int value){
int middleIndex = ((list.size()+1) / 2) - 1;
if (list.size() == 0){
result = "YOK";
}else{
if (value == list.get(middleIndex)){
result = "VAR";
}else if (value > list.get(middleIndex)){
list = list.subList(middleIndex+1, list.size());
binarySearch(list, value);
}else{
list = list.subList(0, middleIndex);
binarySearch(list, value);
}
}
}
Binary Search algoritmasında bildiğiniz üzere arama yapılmadan önce liste sıralı olarak verilmelidir.
Ek olarak neden iki seçenek ile örnek yaptık derseniz burada dikkat etmemiz gereken noktalardan birisi de algoritmaların performansını karşılaştırmaktır.
İlk yaptığımız örnekte aranan değer mevcut listedeki her eleman ile tek tek karşılaştırılacaktı ve her ne olursa olsun bütün elemanlar tek tek gezilecekti.
Fakat 2. örneğimizde Binary Search algoritması kullandık ve en büyük avantajından birisi burada performans oldu çünkü liste sıralı olarak kontrol edileceği için liste her seferinde 2 ye bölünerek kontrol edilecekti. Buradan üssel fonksiyonun tersi logaritmik fonksiyon olduğunu düşünürsek Binary Search algoritması log2(n) (logaritma 2 tabanında n) süresince daha performanslı çalışır. Buradaki n listedeki eleman sayısını ifade etmektedir.
Proje Kodu : Github
Eğer bu tip algoritma sorularına meraklıysanız burada bolca, her seviyeye göre sorular mevcut.
Faydalı bir yazı olması dileğiyle hoşçakalın.
11