Java

Binary Search Implementation

23 Nisan 2018

Merhabalar. Elimizde şöyle bir senaryo olduğunu düşünün:

  • 1 milyon tane sayıdan oluşan bir array var.
  • Bu arraydeki tüm sayılar sıralı bir şekilde dizilmiş olsun.
  • Amacımız bu arrayin içinde belli bir sayını bulabilmek.

Bunu nasıl yapardınız? Akla gelen ilk yöntem, arrayin içindeki tüm sayılara tek tek bakıp, aradığımız sayıyı bulmaya çalışmak. Ancak bu yöntem hiç de verimli (efficient) bir yol değildir. En kötü ihtimalle aradığımız sayı en sondaysa, bütün arrayi dolaşmamız gerekecek. O zaman öyle bir kod yazalım ki, bir baştan bir sondan sayıya baksın. Bu sefer de en kötü ihtimalle sayı tam ortadaysa tüm arrayi dolaşmamız gerekecek. Yani “time complexity” dediğimiz şey O(n) olacak. Burada “n” değeri arrayin uzunluğu. Programlama dilinde bu tarz basit arama işlemlerini O(n) time complexity ile yapmak hiç de verimli değildir.

Özellikle kullandığımız array sıralı bir arrayse, kesinlikle bu yöntemi kullanmayacağız. Daha iyi bir yöntem olan, Binary Search dediğimiz ikili arama yöntemini kullanacağız. İzleyeceğimiz prosedür şu şekilde:

  1. Önce arrayin tam ortasındaki sayıya bakıyoruz ve arrayimizi bu noktadan ikiye böldüğümüzü düşünüyoruz. Bunlara sol array ve sağ array diyelim.
  2. Eğer bu sayı, bizim aradığımız sayıdan büyükse, sol arraye bakacağız. Küçükse, sağ arraye bakacağız.
  3. Yukarıdaki işlemleri tekrarlayarak ilerleyeceğiz.
  4. Aradığımız sayıyı bulana kadar bu işlemi yapıyoruz. Eğer bulamazsak, -1 sonucunu bize return edecek. Eğer bulursak, sayının indexini return edecek.

Bu şekilde ikiye bölerek ilerleme işlemine, “Divide and Conquer” yani “Böl ve Fethet” yöntemi deniyor. Basit bir örnekle başlayalım isterseniz.

Elimizde şöyle bir sıralı array olsun ve aradığımız sayı da 1114 olsun.

Bu arrayde ortadaki sayımız 112. Doğal olarak o noktadan başlayacağız. 112 < 1114 olduğu için sağ arraye bakacağız. Bundan sonra artık yeni arrayimiz şu şekilde olacak:

Orta noktamız artık 2223 oldu. 2223 > 1114 olduğu için bu sefer sol arraye bakacağız. Artık elimizde sadece 512 ve 1114 var. Şimdi, orta noktayı nasıl bulacağız? Burası aslında sizin kodu nasıl yazdığınızla alakalı olacak. Eğer soldakini alacak şekilde yazarsanız soldakine bakar, aksi halde sağdakine bakar. Diyelim ki, sola göre kod yazdık. Bu sefer 512’ye bakacağız. 512 < 1114 olduğu için sağ arraye bakacağız. Elimizde sadece 1114 kaldı ve aradığımız sayı da zaten buydu. Binary Search bize o sayının indexini return ettiği için 1114’ün indexini return edecek. Bu noktada outputumuz 4 olacak.

Şimdi, gelelim Binary Search’ü Java’da nasıl implement edeceğiz. İki şekilde yapabiliriz. Biri recursive olarak metodumuzu çağırarak, diğeri ise iterative olarak. Önce recursive olarak yazmaya çalışalım.

Recursive Binary Search Implementation

Yapmaya çalıştığımız şey, arrayi sürekli ikiye bölerek ilerlemek. Her adımda da arrayimizin başlangıç ve son değerleri değişiyor. Yukarıdaki örnekte, ilk arrayimiz ikiye bölündüğünde artık yeni arrayimizi 22’den değil de 512’den başlamıştı. O zaman bizim arrayin alt ve üst noktalarına ihtiyacımız olacak. Yani metodumuzu çağırırken parametre olarak bunları alalım. Recursive olarak yazdığımız için, metodu çağırırken, yeni alt ve üst noktalarıyla çağıracağız. Sonuçta parametrelerimiz:

  1. Kullanacağımız array.
  2. Başlangıç indexi.
  3. Bitiş indexi.
  4. Aradığımız sayı.

Sonuç olarak yaptığımız işlem şu:

  • Ortadaki değer aradığımız değere eşitse, o anki indexi return et.
  • Ortadaki değer aradığımız değerden büyükse sola bak.
  • Ortadaki değer aradığımız değerden küçükse sağa bak.

Iterative Binary Search Implementation

Recursive metoddan farklı olarak iterative metodda sadece iki parametreye ihtiyacımız var. Kullanacağımız array ve aradığımız sayı. Yapacağımız işlem şöyle:

  • Başlangıç noktamız 0. index ve bitiş noktamız ise arrayin son elemanı olacak.
  • Başlangıç ve bitiş noktamız her adımda birbirine yaklaşacak ve başlangıç noktamız artık bitiş noktamızdan küçük olmadığında döngüyü durduracağız.
  • Bu sırada, yine orta noktayı her adımda güncelleyeceğiz ve eğer aradığımız eleman orta noktaya eşitse, o anki orta noktayı return edeceğiz. Aksi halde başlangıç veya bitiş noktamızı değiştireceğiz. Ama bunu yaparken de dikkatli olmamız lazım. Koda bakınca ve kodu kendiniz trace edince bunu fark edeceksiniz zaten.

İkisinde de output şöyle olacak:

Bulunan elemanın indexi: 4

Bunları yaptıktan sonra artık konunun en başında bahsettiğim time complexity meselesine gelelim. Sonuçta yazdığımız her algoritmada en çok dikkat ettiğimiz noktalardan birisi time complexitydir. Algoritmamızın verimli bir şekilde çalışması için elimizden geleni yaparız. Peki, Binary Search algoritmasının time complexitysi nedir?

Binary Search Time Complexity

İsterseniz adım adım hesap yapalım. Her adımda arrayimiz yarıya bölünüyor ve her adımda bazı karşılaştırmalar yapıyoruz. Yaptığımız karşılaştırmalar bizim “constant time” dediğimiz sürede gerçekleşiyor. Yani o kadar küçük ki, bir sabit sayı olarak görebiliriz. Buna genelde “1” diyoruz. Arrayimizin uzunluğu da “n” olsun. O zaman ilk formülümüz şöyle başlayacak.

T(n) = T(\displaystyle\dfrac{n}{2}) + 1

Daha sonra diyelim ki, ikinci adım oldu. Bu sefer “n” yerine “n/2” koymamız gerekiyor, çünkü her adımda arrayimiz yarıya iniyor. Doğal olarak “n” değerimiz de ikiye bölünecek. O zaman:

(T(\displaystyle\dfrac{n}{4}) + 1) + 1

şeklinde bir şey elde edeceğiz. Bir adım daha gidelim. Yani “n/2” yerine “n/4” yazalım.

(T(\displaystyle\dfrac{n}{8}) + 1) + 2

Sanırım yavaş yavaş görmeye başladınız. 3. adımda 2 üssü 3 yani 8 oldu paydada. Aynı zamanda sabit olan sayımız da 3c oldu. Yani 4. adımda payda 16 olurken sabit olan sayı da 4c olacak. O zaman formülü şöyle yapalım:

T(\displaystyle\dfrac{n}{2^k}) = T(\frac{n}{2^{k+1}}) + (k+1)

Şimdi, 2^k \rightarrow n yaptığımızda, k \rightarrow log_{2}{n} olacak ve birazcık da cebir kullanırsak, artık elimizde şu denklem olacak:

T(1) = T(\dfrac{1}{2}) + log_{2}{n} + 1

Complexity hesaplarken sabitleri yani “constant” değerleri göz ardı ediyoruz. Bunu yaptıktan sonra elimizde sadece log_{2}{n} kalıyor.

Binary Search ile kodumuz ne kadar hızlandı?

Bunu anlamanın bir kaç yolu var. İsterseniz matematik hesabı yaparsınız direkt olarak. İsterseniz canlı olarak görmek için Java’da kodunuzun çalışma hızına bakarsınız. Önce matematik hesabını yapalım. Yazının başında aradığımız sayıyı bulmanın yolu olarak elemanlara tek tek bakmayı önermiştik. Yani en kötü ihtimalle tüm arrayi dolaşmamız gerekecekti. Bunun için O(n) time complexity gerekiyor dedik. Yani 1 milyon elemanlı bir arrayde aradığımız elemanı bulmak 1 işlem gerektirecek en kötü ihtimalle. Binary Search için ise O(log_{2}{n} demiştik. Hesap makinesinde log_{2}{1000000} hesaplarsınız yaklaşık 20 değerini bulacaksanız. Sanırım kodumuzun ne kadar hızlandığını daha iyi bir şekilde görmüş olduk. Şimdi, canlı bir örnek yapalım. Bunun için O(n) ile çalışacak olan bir Java kodu yazalım. Arama işlemini lineer olarak yazdığımız için buna “linearSearch” ismini vereceğim.

Bunu yaptıktan sonra kodumuzu iyi bir şekilde test edebilmek için elimizde büyük bir array olmalı. Bunun için de 500 bin elemanlı bir array oluşturacağım. Ancak arrayi oluştururken elemanların büyükten küçüğe veya küçükten büyüğe olması gerekiyor. Sayıların ne olduğunun bir önemi yok. Örnekte kolaylık olması açısından arrayi 0’dan 499999’a kadar dolduracağım. Bu şekilde kodumuzun doğru bir şekilde çalıştığından daha rahat emin olacağız. Yazdığım metoda “arrayGenerator” ismini veriyorum ve bu metod “n” parametresini alıyor ve bu parametre uzunluğunda bir array oluşturuyor.

Geçen süreyi nasıl hesaplayacağız?

Her şey çok iyi ama Binary Search’ün ne kadar sürede bulduğunu nasıl bileceğiz? Bunun için de Java’nın System classının içindeki “nanoTime()” metodunu kullanacağız. Kodumuzu çalıştırmadan önce sistemin o anki zamanını bir long değişkeninde saklayacağız. Metodu çalıştırdıktan sonraki zamanı da başka bir long değişkeninde tutacağız. Bu iki değişkeni birbirinden çıkardığımızda kodun ne kadar sürede çalıştığını görmüş olacağız.

Yani kodumuz şu şekilde olacak:

Recursive Binary Search ve Linear Search metodlarını karşılaştırmak istiyorum. 500000 elemanlı bir test arrayi oluşturdum. İlk olarak Binary Search’ün running time süresine yani kodu çalıştırma süresine bakıyorum. Daha sonra da aynı teknikle Linear Search’ün çalışma süresine bakıyorum. Bu değerler her defasında farklı çıkabilir. Ama yakın değerler çıkacaktır. Bu arada aradığım sayı “350000“. Büyük bir sayı seçmemin sebebi aradaki farkı net bir şekilde görebilmek. Sonuç olarak bende verdiği output şöyle:

10759
2802603

Yani Binary Search 10 bin nanosaniyede çalışıyorken, Linear Search 2802603 nanosaniyede çalıştı. Binary Search 260 kat daha hızlı çalışmış oldu.

Sonuç

Sonuç olarak eğer elimizde sıralı bir array varsa ve bu arrayde bir sayıyı bulmak istiyorsak, Binary Search ile bunu rahatlıkla yapabiliyoruz. Şunu da unutmamak gerekir ki, eğer iyi ve etkili bir kod yazdıysanız, sizden kat kat daha iyi bir bilgisayara sahip kişiden daha hızlı bir şekilde çalışabilirsiniz. Yukarıda lineer arama işlemini yaparak kodunu çalıştıran birinden 260 kat daha hızlı olabilirsiniz mesela.

    Bir Cevap Yazın

    This site uses Akismet to reduce spam. Learn how your comment data is processed.