Rehber İkili arama algoritması: Binary Search

Merhaba,

Sosyal'de farklı tarzda bir paylaşım olarak ünlü algoritmalardan birinin anlatımını yapmak istedim. Umarım keyif alırsınız, bakalım. Anlatımın uzunluğunu düşününce başta çok üşendim de düşünmüşken yapalım da Sosyal'e katkımız olsun, değil mi?

Algoritmayı başta genelde kullanılan tanıtım örneğiyle anlatacağım ve sonrasında biraz daha genelleştireceğim. Algoritmanın isminin Türkçe karşılığı olan "ikili arama"yı kullanmak hoşuma gitmiyor ve dolayısıyla yazı boyunca İngilizce olan "binary search" ismini tercih edeceğim.

Doğrusal arama (linear search) yöntemi​

Elinizde sıralı bir sayı listesi olduğunu düşünün; ister küçükten büyüğe, ister büyükten küçüğe. Anlatım kolaylığı için küçükten büyüğe sıralı olsun:

3, 6, 11, 11, 13, 15, 20, 100, 271, 314, 1000​

Bu sıralı listede herhangi bir sayıyının bulunup bulunmadığını kontrol etmek istersek ne yapabiliriz?
Akla gelen ilk yöntemlerden biri, baştan başlayıp tek tek kontrol etmek: 3, 6, 11,... Bu kontrole doğrusal arama (linear search) deniyor, elimizin ilk gittiği arama çeşitlerinden biri.

Birkaç doğrusal arama örneği:

• -1 var mı?
  • İlk sayı olan 3, -1'den büyük. Liste sıralı olduğu için gerisine bakmaya gerek yok. -1 bu listede bulunmuyor.
• 6 var mı?
  • İlk sayıya baktık: 3, 6'dan küçük. İkinci sayıya baktık: 6. Demek ki 6 var.
• 14 var mı?
  • 5. sayı olan 13'e kadar gelmemiz gerekir. Sonrasında 15'e geliriz ve 14'ün olmadığını anlarız çünkü listenin gerisi kesin 15'ten büyük veya 15'e eşit sayılar içeriyor.
  • 6 sayı kontrol etmiş olduk.
• 15 var mı?
  • Tıpkı 14'te yaptığımız gibi 15'e kadarki sayıları tek tek kontrol ederek 6 sayıdan sonra 15'in bulunduğunu anlarız.
• 314 var mı?
  • Burada listenin başından başlayınca çok fazla kontrol gerekiyor ama sondan başlasak çok daha erken anlarız; ama burada dikkat edin ki bir önceki örnekteki 15 listenin tam ortasındaydı: Baştan da sondan da başlasak listenin yarısını gezmemiz gerekecekti.

Kendiniz de başka sayılar deneyerek veya denemeden direkt tahmin ederek doğrusal arama yöntemiyle en kötü durumda listenin tümünü gezeceğinizi görebilirsiniz. Evet, bazen sondan başlamak baştan başlamaya göre daha avantajlı olabiliyor ama hangi başlangıcın daha avantajlı olduğunu bilemezsiniz aslında.

Ee, binary search neyin nesi peki?​

Baştan veya sondan başlamayalım, onun yerine ortadan başlayalım, ne dersiniz? Hatta listemizi birazcık büyütelim:

-5, 3, 6, 11, 11, 13, 14, 15, 17, 19, 20, 100, 150, 225, 260, 260, 271, 300, 314, 600, 758, 999, 1000​

Uf, iyi uzadı.

Normalde kod yazacak olsak orta pozisyonu net bir şekilde liste_uzunlugu/2 formülüyle bulabilirdik fakat burada biraz göz kararı gidebiliriz:

• 271 var mı?
  • Listenin ortasında 150 duruyor gibi. 150, 271'den küçük bir sayı. Bu bilgiyi nasıl kullanabiliriz?
    • Şimdi buraya iyi bakın, binary search'ün yararlandığı özelliği kullanacağız. Kendiniz de bir süre düşünebilirsiniz: Liste küçükten büyüğe sıralı. Dolayısıyla, 150, 271'den küçükse 150'nin solundaki tüm sayılar da 271'den küçüktür.
      
      Devam etmeden önce lütfen yukarıdaki spoiler'ı okuduğunuzdan emin olun.
      
      Bu gözlemi avantaja çevirmek için listenin 150 ve kendisinden önceki tüm kısmını görmezden gelebiliriz çünkü 271 varsa da oralarda bir yerde olamaz, yani artık sadece 225 ile 1000 arasına bakabiliriz. Burada 225 ve sonraki tüm sayıları ele almamız gerekiyor çünkü görmezden gelmek için makul bir nedenimiz yok, 150 ve gerisi için vardı.
  • 225 ile 1000'in ortasında 300 duruyor (314'ü de seçebilirsiniz). 300, 271'den büyük bir sayı. Önceki durumdan biraz farklı ama aslında benzer: Liste sıralı olduğu için 300 ve kendisinden sonraki tüm sayılar 271'den büyük. Bu yüzden 300 ve sonrasını görmezden gelebiliriz.
  • 225 ile 271 arası kaldı artık. Evet, biliyorum, 271 gözümüzden önünde işte. Anlayış gösterin, belirli bir yöntem kullanıyoruz şurada! (Bağırmadım, şaka şaka.)
    Listenin ilgilendiğimiz kısmı şu an sadece 4 sayı içeriyor. Siz saymayın, ben söyleyeyim: Listede toplam 23 sayı var. Bakın, sadece 2 adımda 19 sayıyı eledik bile. Bu sizce nasıl oldu? Düşünün bir. Devam edelim: Ortada 2 tane 260 var. Hadi, sağdakini seçmiş olalım. 260, 271'den küçük olduğu için 260 dahil sol tarafı göz ardı edebiliriz.
  • Kaldık sadece 271 ile. Demek ki var mış. Herhangi bir uçtan başlayıp doğrusal arama yöntemini kullansaydık daha çok sayıyı kontrol etmemiz gerekecekti. Ee, beğendiniz mi birazcık? Beğendiniz, beğendiniz. (Yoksa bozuşuruz...)
• 271'i 3 adımda bulduk. Normalde algoritmayı kodluyor olsaydık sağdaki değil soldaki 260'ı seçerdik büyük ihtimalle, o yüzden bir adım daha eklenirdi aslında. Şimdi 16'ya bi' bakalım, arama yöntemimiz aynı şekilde ortalardan ilerlemek olacak:
  • 150, 16'dan büyük. 150 ve ilerisini göz ardı edebiliriz.
  • -5 ile 100'ün ortasında 14 var gibi. 14, 16'dan küçük. 14 ve gerisini göz ardı edebiliriz.
  • 15 ile 100'ün ortasında 19 var. 19, 16'dan küçük. 19 ve ilerisini göz ardı edebiliriz.
  • 15 ile 17'nin ortası yok ama 15 diye varsayabiliriz. 15, 16'dan küçük olduğu için 15'i göz ardı edebiliriz, gerisi de yok zaten.
  • Elimizde sadece 17 kaldı, yani 16'nın en azından bulunma ihtimalinin olabileceği aralıkta sadece 17 kaldı. Bu demek oluyor ki 16 listede bulunmuyor.

16'nın da listede bulunmadığını 5 adımda bulduk. Merak ettiyseniz herhangi bir sayının varlığını en fazla 5-6 adımda kontrol edebiliyoruz bu yöntemle.

Nasıl daha hızlı oldu bu binary search böyle?​

Her adımda listenin ilgilendiğimiz kısmın yarısını "çöpe atıyoruz", bu sayede kontrol aralığımız yarı yarıya daralıyor. Ne zaman karara varıyoruz? Elimizde tek sayı kalınca. Aradığımız sayıya eşitse eşit, değilse değil. Aralıkta ne zaman tek bir sayı kalıyor? "Liste uzunluğunu kaç kere 2'ye bölersek 1 elde ederiz?" sorusunun cevabıyla aynı.

Anlatım gereği görece az sayı içeren bir listeyi örnek aldık: 23 sayıcık. Liste 1 milyon adet sayı içerse en fazla kaç adım sürecekti binary search? İkiye böle böle gidelim bakalım:

1. 1.000.000
2. 500.000
3. 250.000
4. 125.000
5. 62.500
6. 31.250
7. 15.625
8. 7.812 (Sonuçta aralıktaki sayıların sayısı bir tam sayı olacak.)
9. 3.906
10. 1.953
11. 976
12. 488
13. 244
14. 122
15. 61
16. 30
17. 15
18. 7
19. 3
20. 1

Tabii 1-2 adım fark edebiliyor ama yaklaşık en fazla 20 adım ediyor gördüğünüz üzere. Dikkat edin ki 20, binary search'ün en kötü çalıştığı durumdaki adım sayısı olurdu. Örneğin en iyi durum direkt ortadaki sayının aradığımıza eşit olması olurdu, 1 adımda çalışırdı. Aranan sayıya göre binary search, 1 milyon sayılık bir liste için 1 ila 20 arasında herhangi bir sayıda adım gerektirebilir.

Genel olarak liste n adet sayı içerirse binary search bir sayının varlığını en fazla yaklaşık log2(n) adımda kontrol edebiliyor.

Özet olarak binary search, sıralı listede sayı aramada sıralılık avantajından faydalanıp kontrol aralığını yarı yarıya daralta daralta giden bir yöntem.

Tam nasıl yapıyoruz yani?​

Şimdiyse binary search algoritmasını genel olarak programlama jargonuyla anlatayım:

1. Başta kontrol ettiğimiz aralık, listenin tamamı. Aralığın başında 1. sayı, sonunda sonuncu sayı (n'inci) var. Yani [1, n] aralığına bakıyoruz. Kod yazacak olsak [0, n - 1] derdik tabii, hatta öyle devam edelim aslında.
   • Aralığın uçlarına isim verelim: l ve r. Başta l = 0 ve r = n - 1.
2. Aralığın ortasındaki sayıya bakmak için orta pozisyonu (index) bulmamız gerekiyor. Bu, aralığın başıyla sonunun aritmetik ortalamasına denk gelir. Eğer ortalama ondalıklı (.5'li) gelirse aşağı yuvarlarız. (C++'ta bölme operatörü olan / bu şekilde çalışır.)
   • Orta pozisyona isim verelim: mid.
3. Eğer mid'de bulunan sayı (liste[mid]) varlığını kontrol ettiğimiz sayıdan küçükse (x), yani liste[mid] < x ise biliriz ki listenin [l, mid] aralığındaki sayıların hepsi x'ten küçüktür. Bundan dolayı aralığın sol ucunu yani l'yi mid + 1'e çekebiliriz. Durum tam tersiyse yani liste[mid] > x ise bu sefer de [mid, r] aralığındaki sayıların hepsi x'ten büyüktür. Bu durumda aralığın sağ ucunu yani r'yi mid - 1'e çekebiliriz. Eğer liste[mid] == x ise (çoğu yazılım dilinde çift eşittir sembolü, değerlerin eşitliğini kontrol eden eşitlik operatörünü temsil eder) zaten sayının var olduğunu tespit etmişizdir.
   • Burada aslında 3 farklı durumu kontrol ettik: küçüklük, büyüklük ve eşitlik. Kodu kısaltmak için büyüklük ve eşitlik birleştirilip "büyük eşitlik" (>=) durumu kontrol edilebiliyor ki ben hep bunu kullanırım. Böyle yapılırsa r = mid - 1 değil r = mid yapılması gerekir çünkü liste[mid], aranan sayıya eşit olma ihtimali olan bir sayı olmuş oluyor. Fark ettiyseniz göz ardı etme şartımız, göz ardı edilen aralıkta aranan sayının kesin bulunamayışı.

Büyükten küçüğe sıralı olan bir liste için ne yapılması gerektiğini düşünmeyi size bırakıyorum.

Biraz da kod paylaş!​

[CODE lang="cpp" title="C++ binary search kodu"]int n = 1'000'000; // Listedeki sayıların sayısı.
int liste[n] = {...}; // Küçükten büyüğe sıralı olsun.
int x = 2024; // Varlığı kontrol edilecek sayı.
int cevap = -1; // Aranan sayının pozisyonunu arayalım. Eğer bulamazsak -1 olsun.
int l = 0, r = n - 1; // Binary search aralık uçları.

// Aralıkta birden fazla sayı varken binary search devam etsin.
while (l < r) {
// Aralığın orta pozisyonu.
int mid = (l + r) / 2;
if (liste[mid] < x) {
// [l, mid] aralığında x bulunamaz.
l = mid + 1;
} else if (liste[mid] > x) {
// [mid, r] aralığında x bulunamaz.
r = mid - 1;
} else {
// Açıklamaya gerek var mı?
cevap = mid;
break;
}
}

// Sayı bulunamadıysa cevap -1 oluyor.
// [0, n-1] aralığının dışında bir sayı olduğundan, -1 değerini bu amaç için kullanabiliyoruz.[/CODE]

[CODE lang="python" title="Python binary search kodu"]# Python'a yorum yok
n = 1_000_000
liste = [...]
x = 2024
cevap = -1
l, r = 0, n - 1
while l < r:
mid = (l + r) // 2 # Tek / kullanmayın!
if liste[mid] < x:
l = mid + 1
elif liste[mid] > x:
r = mid - 1
else:
cevap = mid
break[/CODE]

Ek olarak bahsettiğim, sadece iki koşulu kontrol eden benim kullandığım implementasyon:
[CODE lang="cpp" title="C++ iki koşullu binary search kodu"]int n = 1'000'000; // Listedeki sayıların sayısı.
int liste[n] = {...}; // Küçükten büyüğe sıralı olsun.
int x = 2024; // Varlığı kontrol edilecek sayı.
// Cevabın ekstra bir değişkende tutulmasına gerek yok, l cevap olacak.
// Binary search aralık uçları.
int l = 0, r = n - 1;
// Aralıkta birden fazla sayı varken binary search devam etsin.
while (l < r) {
// Aralığın orta pozisyonu.
int mid = (l + r) / 2;
if (liste[mid] < x) {
// [l, mid] aralığında x bulunamaz.
l = mid + 1;
} else {
// liste[mid] >= x
// liste[mid] == x olabilir, bu yüzden r = mid - 1 değil r = mid.
r = mid;
}
}
// Burada aslında l, listede x'ten büyük ve x'e eşit olan ilk elemanı (liste[l] >= x) işaret ediyor.
// [Bu biraz detay olduğu için değinmemiştim, kendiniz nedenini düşünün lütfen ]
// Yani liste[l] == x diye ek kontrol gerekiyor.[/CODE]

Binary search uygulanabilirliğinin genel koşulu​

Örnek olarak sadece verilen sıralı listede bir sayının varlığını kontrol etmeyi ele aldık. Sıra, binary search uygulanabilirliği için gerekli koşulları genelleştirmeye geldi.

Binary search'ün uygulanabilirliği, arama şartının listedeki bir noktaya kadar sürekli sağlanmasını, o noktadan sonra da asla sağlanmamasını gerektiriyor. Tam tersi de olabilir: Bir noktaya kadar şart asla sağlanmaz, o noktadan sonra da sürekli sağlanır.

Örneğin, küçükten büyüğe sıralı bir listede bir sayının varlığının kontrolü için aslında liste[i] < x şartını kullanıyoruz. Bunu sağlamayan en küçük i değeri için eğer liste[i] == x oluyorsa o zaman x'in listede olduğuna kanaat getiriyoruz. Bu şartın sağlanmasını 1 ve sağlanmamasını 0 ile gösterirsek, listedeki tüm sayılar için şöyle bir görüntü ortaya çıkar:

1, 1, 1,..., 1, 1, 0, 0, 0,..., 0, 0, 0​

İşte biz buradaki ilk 0'ın pozisyonunu bulmaya çalışıyoruz binary search ile. O pozisyondaki değer x'e eşitse sayı var, değilse yok diyebiliyoruz. Bulunurluk kontrol etme binary search'ü aslında verilen sayıdan küçük olmayan ilk sayının pozisyonunu buluyor.

Daha da genelleştireyim: binary search'ün uygulanabilmesi için eşitsizlik şartında listedeki sayılara uygulanan fonksiyon monotonik (sürekli artan ya da sürekli azalan, daha doğrusu non-decreasing ya da non-increasing) olmalı. Şimdi böyle deyince kafanız biraz karışmış olabilir, birazdan vereceğim örneklerle daha iyi anlaşılacaktır umarım. Mesela bulunurluk kontrol etme metodunda liste[i] < x eşitsizlik şartında uygulanan fonksiyon birim fonksiyon, yani direkt listedeki sayının kendisi. Hemen başka örnekler vereyim:

• Verilen sayının karekökünün aşağı yuvarlanmış halini bulma: Listemiz doğal sayılar direkt. Şart ise (düşünebilirsiniz) sayı * sayı <= x. Uygulanan fonksiyon f(sayı) = sayı * sayı yani ünlü f(x) = x^2 fonksiyonu.
• Absürt bir örnek: x^6 + 2024x^2 + 67x + 181951 = 1337420 eşitliğini sağlayan x değeri nedir? Burada "liste"miz reel sayılar. Şartımızsa sadece eşitliğin eşitsizliğe dönüşmüş hali.
  • Burada aralık uçlarının ondalıklı sayı olması gerekiyor.
• Doğal sayılar içeren bir listede kendisine kadarki sayıların toplamının en fazla 1 milyon olduğu son pozisyon. Burada prefix sum tekniğini düşünmeniz gerekiyor.

Burayı biraz kısa bıraktım, en önemli kısımlardan biri aslında. Umarım çok kafanızı karıştırmamışımdır.

Örnek problemler ve Codeforces kursu​

Geldik eğlenceli kısma. Örnek birkaç binary search problemi paylaştım:

• Problem - 1915C - Codeforces
• Find First and Last Position of Element in Sorted Array - LeetCode
• Sqrt(x) - LeetCode
• Courses - Codeforces
  • Codeforces'ın binary search kursu. "No such course" diyerek girmenizi engelleyebilir, yönlendirdiği sayfada "ITMO Academy: pilot course" isimli kursa kaydolmanız gerekiyor, sonrasında binary search kursuna girebilirsiniz. Kursta hem eğitim hem de bol bol soru var.

Ek kaynak (Errichto'nun binary search videosu), zamanında çok keyifle izlemiştim:
Umarım sizlere faydası dokunur bu rehberin. Binary search, temel olmasına karşın en sevdiğim algoritmalardan biri. Kendisini sizlere tanıtma fırsatı elde ettiğim için oldukça keyifliyim.

Hiç yazmıyordum, burada ilk kez yazayım:

İyi Sosyal'ler! ​