Lineer Search ve Binary Search (in Java)

Fatih GÜL
Sep 2, 2018 · 3 min read

Önceki yazımda Java’da dizi yapısının nasıl implemente edildiğini ve insert, delete, search gibi işlemlerin nasıl yapıldığını anlatmıştım.Bu yazıda Java’da ordered(sıralı) ve unordered(sıralı olmayan) dizi yapılarını ve bu yapıların search işlemi üzerindeki etkisinden dolayısıyla da lineer search ve binary search işlemlerinden bahsedeceğim.

Unordered(Sıralı olmayan) dizide, içeresindeki elemanların sıralanmasında veya sırasında belirli bir düzen yoktur.Örneğin oluşturduğumuz int tipindeki diziye rastgele ürettiğimiz sayıları yerleştirelim.Dizideki sayıların sıralamasında büyükten küçüğe yada küçükten büyüğe bir sıralama veya düzen yoktur.

Bir de Ordered yani sıralı dizi vardır.Bu dizinin içeresindeki elemanlar belirli bir düzene göre (büyükten küçüğe veya küçükten büyüğe doğru) sıralanmıştır.Örneğimizde küçükten büyüğe doğru sıralama yapılmıştır.

Ordered ve Unordered dizi ne demektir bunu açıkladıktan sonra birini diğerine neden tercih etmeliyim? Her ikisi de data structure olarak array tipinde olmasına rağmen verilerin sıralanışı farklıdır ve bu farklılık aslında yerine göre müthiş bir avantaja dönüşür.

Daha önceki yazılarımda belirttiğim gibi dizi üzerinde search, insert, delete gibi işlemleri yapabiliyorum.Kısa bir özet yapacak olursam; elimdeki diziyi aslında bir container(index bazlı container) gibi düşünebilirim. Index’i sıfırdan başlayıp bir artarak devam eder ve her index numarası bir elemana işaret eder. Şimdi dizi üzerindeki search işleminden başlayalım ve bu işlemi her iki dizi yapısı içinde(ordered ve unordered ) gözlemleyelim.

Lineer Search:

Dizide ki elemanlarımız unordered bir şekilde dizilmişse ve biz bu dizi içerisinde arama yapmak istiyorsak başvuracağımız yöntem lineer search’ tür.Yani aramak istediğim terim(key) için dizinin bütün elemanlarını sırası ile dolaşmam gerekiyor.Özetle dizinin içeresindeki her bir elemanın kapısını sırasıyla çalıp aradığım elemana bakıyorum. Aradığım eleman, şanslıysam dizinin ilk elemanı olabilir, dizinin ortasında olabilir veya şansım yoksa aradığım key bu dizide olmayabilir.Performans açısından en iyi ihtimalle ilk denemede bulurum ki, bu iyi bir performans sayılır yada en kötü ihtimalle dizinin boyutu kadar efor harcayabilirim ki, bu da performans açısından kötüdür.Gördüğümüz gibi basit bir mantığı var.

Binary Search :

Binary Search işlemi yapabilmem için bir ön koşul vardır. Binary Search yapacağım dizi kesinlikle ordered dizi olmalıdır. Durum böyle olunca Binary Search işlemi Lineer Search işlemine göre daha hızlı olur. Özellikle dizinin boyutu çok büyükse neredeyse performans açısından ikiye katlayabilir.

Çocukluğumuzdan bildiğimiz sayı tahmin oyunu binary search için iyi bir örnek olacaktır. Sayı tahmin oyununu hatırlayalım: Karşımızdaki kişi 1-100 arasında bir sayı tutuyor ve biz aklında tuttuğu sayıyı tahmin etmeye çalışıyoruz. Söylediğimiz her sayıya 3 şekilde cevap verebilir; ya yukarı çık 👆, ya aşağı in 👇, yada bildin 👌. Böyle bir durumda nasıl bir strateji izlenmeli ki en az tahminde tuttuğu sayıyı bilebileyim.Sayı aralığının her zaman ortasındaki sayıyı söyleyerek en az eforla sayıyı tahmin edebilirim.Diyelim ki 33 sayısını tuttu ve ben tahmin etmeye çalışıyorum.İlk 1–100 arasındaki ortadaki sayı 50 ‘yi söylerim 👇 , ikinci hakkımda bilemeyince 1–49 arasında olan ortadaki sayı 25’i denerim 👆, yine başarısız olunca 26–49 arasındaki ortadaki sayı 37 söyleyince 👇, yılmak yok devam bu sefer 26–36 arasında 31 derim 👆, sanırım yaklaştım 32–36 arasında 34 derim ama 👇, çok yaklaştım 32 👆 , işte 33 👌.

Bunu tablo haline getirirsek:

Sayı tahmin oyununda lineer search algoritmasını kullansaydım 1'den başlayarak tam 33 denemeden sonra doğru sonuca ulaşacaktım.Ama Binary Search algoritmasını kullanarak 7 tahminde bu işi başarabildim.Evet sadece dizideki sayıları sıralayarak ve uygun algoritmayı kullanarak performans kazancım arttı.

Sonuç olarak dizide search işlemi yapmak istiyorsam binary search mantıklı bir seçenek olarak duruyor.Dizide ekleme ve silme gibi işlemler yapmak istediğimde dizinin ordered veya unordered olması search işlemindeki gibi büyük bir performans kazancı sağlamıyor.Bunun için daha farklı seçenekler masaya yatırmamız gerekiyor.Sonraki yazılarda bu konulara değineceğim.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade