Binary Search Derinlemesine: Lower Bound, Off-by-One ve Cevap Üzerinde Binary Search

Sürüm notu: Bu yazıdaki kodlar .NET 10 ve C# 14 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır.

Önce Tahmin Et

Bookstore'un fiyat arşivinde 1.000.000 sıralı fiyat var. Binary search ile bir fiyatı ararken en kötü durumda kaç karşılaştırma yapılır: 1.000 mi, 100 mü, 20 mi?

İkinci soru, bir code review'dan: aşağıdaki method sıralı bir array'de hedeften küçük ya da eşit son elemanın index'ini arıyor. [10, 20] array'inde 20'yi arayınca ne olur?

int lo = 0, hi = sorted.Length - 1;
while (lo < hi)
{
    int mid = lo + (hi - lo) / 2;
    if (sorted[mid] <= target) lo = mid;
    else hi = mid - 1;
}
return lo;

Invariant ile Binary Search Yazmak

Binary search fikir olarak çok basit: sıralı bir array'de ortadaki elemana bak, hedef küçükse sol yarıda, büyükse sağ yarıda aramaya devam et. Her adımda aralık yarıya iniyor; 1.000.000 elemanda en fazla log₂(1.000.000) ≈ 20 adım. İlk sorunun cevabı 20. Ama Jon Bentley'nin Programming Pearls kitabında anlattığı gibi, profesyonel programcıların çoğu ilk denemede hatasız bir binary search yazamıyor. Hataların neredeyse hepsi sınırlarda: hi dahil mi değil mi, mid bir sonraki adımda aralıkta kalıyor mu, döngü ne zaman bitiyor?

Bu hatalardan kaçınmanın yolu, kodu bir invariant'a, yani her adımda doğru kalan bir cümleye göre yazmak. Bu yazıda bütün binary search'ler half-open aralık kullanıyor: arama alanı [lo, hi), yani lo dahil, hi hariç. Başlangıçta hi = Length, aralık boşalınca (lo == hi) döngü bitiyor.

namespace Algorithms.Searching;

public static class BinarySearch
{
    // invariant: hedef varsa [lo, hi) içinde. Aralık her adımda küçülür.
    public static int IndexOf<T>(ReadOnlySpan<T> sorted, T target, IComparer<T>? comparer = null)
    {
        comparer ??= Comparer<T>.Default;
        int lo = 0, hi = sorted.Length;
        while (lo < hi)
        {
            int mid = lo + (hi - lo) / 2; // (lo + hi) / 2 ikisi de büyükken taşabilir
            int cmp = comparer.Compare(sorted[mid], target);
            if (cmp == 0) return mid;
            if (cmp < 0) lo = mid + 1;
            else hi = mid;
        }
        return -1;
    }
}

Her dalı invariant'a göre kontrol edebilirsin. sorted[mid] hedeften küçükse hedef mid'in sağında; mid'i de dışarıda bırakmak için lo = mid + 1. Büyükse hedef mid'in solunda; hi hariç olduğu için hi = mid mid'i zaten dışarıda bırakıyor. İki dalda da aralık en az bir eleman küçülüyor, döngü mutlaka bitiyor.

mid = lo + (hi - lo) / 2 yazımının bir hikâyesi var. (lo + hi) / 2 matematiksel olarak aynı ama lo ve hi ikisi de 2³⁰'dan büyükse toplamları int'in sınırını aşıp negatif oluyor ve array'e negatif bir index'le erişiliyor. Joshua Bloch, Java'nın Arrays.binarySearch'ünde dokuz yıl fark edilmeden duran bu hatayı 2006'da "Nearly All Binary Searches and Mergesorts are Broken" yazısıyla duyurdu. .NET'te bir array 2³⁰'dan fazla elemanlı olabildiği için bu teorik bir risk değil.

Lower Bound ve Upper Bound

Tam eşleşmeyi bulmak, binary search'ün en az kullanışlı hâli. Fiyat listesinde 20 TL'den üç kitap varsa IndexOf bunlardan herhangi birini dönebiliyor. Production'da asıl sorulan sorular şunlar: "20 TL'den küçük olmayan ilk kitap nerede?" (lower bound) ve "20 TL'den büyük ilk kitap nerede?" (upper bound). İkisi de her zaman bir cevap veriyor; hedef yoksa cevap, hedefin sırayı bozmadan eklenebileceği yer.

// target'tan büyük ya da eşit ilk elemanın index'i (ekleme pozisyonu); yoksa sorted.Length
public static int LowerBound<T>(ReadOnlySpan<T> sorted, T target, IComparer<T>? comparer = null)
{
    comparer ??= Comparer<T>.Default;
    int lo = 0, hi = sorted.Length;
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (comparer.Compare(sorted[mid], target) < 0) lo = mid + 1; // mid çok küçük: cevap sağında
        else hi = mid;                                                  // mid cevap olabilir: tut
    }
    return lo;
}

// target'tan büyük ilk elemanın index'i
public static int UpperBound<T>(ReadOnlySpan<T> sorted, T target, IComparer<T>? comparer = null)
{
    comparer ??= Comparer<T>.Default;
    int lo = 0, hi = sorted.Length;
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (comparer.Compare(sorted[mid], target) <= 0) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

public static int CountOf<T>(ReadOnlySpan<T> sorted, T target) =>
    UpperBound(sorted, target) - LowerBound(sorted, target);

Lower bound'un invariant'ı biraz farklı: "cevap [lo, hi] içinde" ve döngü bitince lo == hi cevabın kendisi. sorted[mid] >= target ise mid cevap olabilir; onu kaybetmemek için hi = mid. İki method arasındaki tek fark < ile <=: upper bound eşitleri de "küçük" tarafa atıyor. Aralarındaki fark da hedefin kaç kez geçtiği; sıralı bir array'de "20 TL'lik kaç kitap var?" sorusu iki binary search'le O(log n)'de cevaplanıyor.

private static readonly int[] Prices = [10, 20, 20, 20, 35, 50, 80];

[Theory]
[InlineData(20, 1, 4)]
[InlineData(5, 0, 0)]
[InlineData(21, 4, 4)]
[InlineData(100, 7, 7)]
public void LowerUpperBound_ReturnBoundaries(int target, int lower, int upper)
{
    Assert.Equal(lower, BinarySearch.LowerBound<int>(Prices, target));
    Assert.Equal(upper, BinarySearch.UpperBound<int>(Prices, target));
}

[Fact]
public void LowerBound_MatchesLinearScan_OnRandomData()
{
    Random random = new(21);
    for (int round = 0; round < 200; round++)
    {
        int[] sorted = [.. Enumerable.Range(0, random.Next(0, 50)).Select(_ => random.Next(0, 30)).Order()];
        int target = random.Next(-2, 33);
        int expected = Array.FindIndex(sorted, x => x >= target);
        if (expected < 0) expected = sorted.Length;

        Assert.Equal(expected, BinarySearch.LowerBound<int>(sorted, target));
    }
}

İkinci test binary search'ü test etmenin en güvenli yolu: aynı soruyu doğrusal bir taramayla da sor ve 200 rastgele array'de iki cevabın eşit olduğunu doğrula. Boş array, hepsi aynı değer, hedefin bütün değerlerden küçük ya da büyük olması gibi kenar durumlar rastgele üretimin içinde kendiliğinden çıkıyor.

$ dotnet test --project tests/Algorithms.Tests -- --filter-class Algorithms.Tests.BinarySearchTests
tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64) passed (605ms)

Test run summary: Passed!
  total: 17
  failed: 0
  succeeded: 17

.NET'teki Karşılığı: Array.BinarySearch ve ~index

BCL'deki (Base Class Library) Array.BinarySearch, List<T>.BinarySearch ve MemoryExtensions.BinarySearch lower bound ile tam eşleşmeyi tek bir dönüş değerinde birleştiriyor. Bulursa index'i dönüyor. Bulamazsa Microsoft Learn'deki tanımla, hedeften büyük ilk elemanın index'inin bitwise complement'ini, yani ~index'i dönüyor. Sonuç her zaman negatif ve ~ ile geri çevirince ekleme pozisyonu çıkıyor:

[Fact]
public void ArrayBinarySearch_Missing_ReturnsComplementOfInsertPosition()
{
    int index = Array.BinarySearch(Prices, 40);

    Assert.Equal(-6, index);
    Assert.Equal(5, ~index);
    Assert.Equal(5, BinarySearch.LowerBound<int>(Prices, 40));
}

[Fact]
public void ListBinarySearch_InsertKeepsSorted()
{
    List<int> prices = [10, 20, 35, 50];
    foreach (int price in new[] { 40, 5, 99, 20 })
    {
        int index = prices.BinarySearch(price);
        prices.Insert(index < 0 ? ~index : index, price);
    }

    Assert.Equal([5, 10, 20, 20, 35, 40, 50, 99], prices);
}

~5, yani -6. Neden -1 değil de complement? Çünkü 0. pozisyona ekleme de geçerli bir cevap ve -0 diye bir int yok; ~0 = -1 ise "bulunamadı, başa ekle" anlamına geliyor. İkinci test sıralı bir list'i BinarySearch + Insert ile sıralı tutmanın deyimsel yolunu gösteriyor. Arama O(log n), ama Insert serinin ikinci yazısında gördüğümüz kaydırma yüzünden O(n). Çok sık ekleme yapılan bir sıralı koleksiyon için SortedSet ya da SortedDictionary daha uygun; seçimi C# Koleksiyonlar serisinin "C# Sıralı Collection'lar: SortedList, SortedDictionary, SortedSet ve IComparer" yazısında.

Bir ayrıntı daha: hedef birden fazla kez geçiyorsa Array.BinarySearch'ün hangisini döneceği garanti değil. Dokümana göre yalnızca biri dönüyor ve hangisi olduğu belli değil. İlk ya da sonuncusu gerekiyorsa kendi lower/upper bound'unu yaz.

Cevap Üzerinde Binary Search

Binary search'ün en güçlü kullanımı bir array'de arama yapmak değil, bir cevap aralığında arama yapmak. Bookstore'un deposu sıralı bir koli listesini her gün tek bir kamyonla gönderiyor; koliler sırayla yükleniyor, kapasite dolunca kamyon gidiyor ve kalanlar ertesi güne kalıyor. Bütün koliler 5 günde gitsin diye kiralanacak kamyonun minimum kapasitesi ne olmalı?

Kapasiteyi doğrudan hesaplayan bir formül yok. Ama tersi kolay: kapasite verilince kaç gün gerektiğini tek geçişte hesaplayabiliyorsun. Üstelik bu cevap monotonic: kapasite arttıkça gereken gün sayısı hiç artmıyor. "Bu kapasiteyle 5 günde biter mi?" sorusunun cevabı küçük kapasitelerde hep hayır, bir eşikten sonra hep evet. O eşiği binary search ile bulabilirsin:

// predicate(x) == true olan [lo, hi] içindeki en küçük x; predicate false...false true...true olmalı
public static long FirstTrue(long lo, long hi, Func<long, bool> predicate)
{
    while (lo < hi)
    {
        long mid = lo + (hi - lo) / 2;
        if (predicate(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

public static class Shipping
{
    // bütün kolileri sırayla, "days" gün içinde gönderen en küçük kamyon kapasitesi
    public static long MinCapacity(int[] parcelWeights, int days) =>
        BinarySearch.FirstTrue(parcelWeights.Max(), parcelWeights.Sum(), capacity => DaysNeeded(parcelWeights, capacity) <= days);

    public static int DaysNeeded(int[] parcelWeights, long capacity)
    {
        int daysUsed = 1;
        long load = 0;
        foreach (int weight in parcelWeights)
        {
            if (load + weight > capacity)
            {
                daysUsed++;
                load = 0;
            }
            load += weight;
        }
        return daysUsed;
    }
}

[Fact]
public void MinCapacity_ShipsWithinDays()
{
    int[] parcels = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

    long capacity = Shipping.MinCapacity(parcels, days: 5);

    Assert.Equal(15, capacity);
    Assert.Equal(5, Shipping.DaysNeeded(parcels, 15));
    Assert.Equal(6, Shipping.DaysNeeded(parcels, 14));
}

Arama aralığının sınırları da problemin kendisinden geliyor: kapasite en ağır koliden küçük olamaz (o koli hiç gitmez) ve toplam ağırlıktan büyük olmasına gerek yok (her şey bir günde gider). Testteki ikinci ve üçüncü assert, cevabın gerçekten eşik olduğunu kanıtlıyor: 15 ile 5 gün yetiyor, 14 ile 6 gün gerekiyor. Arama O(log(toplam) · n): her aday kapasite için bir geçiş, log(toplam) aday.

Aynı kalıp şaşırtıcı sayıda probleme uyuyor: belli bir yükü belli bir gecikmeyle karşılamak için gereken minimum sunucu sayısı, bir rapor batch'inin 1 saatte bitmesi için gereken minimum paralellik, bir kitabı N okura bölmek için en büyük bölümün minimum boyutu. Hepsinde ortak olan monotonic bir evet/hayır sorusu: büyüdükçe evet'e dönüp bir daha hayır'a dönmeyen bir şart.

Gerçek Hayat: Log'da Zaman Aralığı ve git bisect

Production'da en sık karşılaşılan binary search, zamana göre sıralı bir şeyde aralık bulmak. Bookstore'un ödeme servisi gün boyunca 30 saniyede bir olay yazan bir log tutuyor; saat 10:00 ile 10:05 arasındaki olaylar isteniyor:

public sealed record LogEntry(DateTimeOffset Time, string Message);

public static class LogSearch
{
    private static readonly Comparer<LogEntry> ByTime = Comparer<LogEntry>.Create((a, b) => a.Time.CompareTo(b.Time));

    // zamana göre sıralı bir log'da from <= Time < to olan kayıtlar
    public static ReadOnlySpan<LogEntry> Between(LogEntry[] sortedLog, DateTimeOffset from, DateTimeOffset to)
    {
        int start = BinarySearch.LowerBound<LogEntry>(sortedLog, new LogEntry(from, ""), ByTime);
        int end = BinarySearch.LowerBound<LogEntry>(sortedLog, new LogEntry(to, ""), ByTime);
        return sortedLog.AsSpan(start, end - start);
    }
}

[Fact]
public void LogSearch_ReturnsHalfOpenRange()
{
    DateTimeOffset t0 = new(2026, 11, 8, 9, 0, 0, TimeSpan.Zero);
    LogEntry[] log = [.. Enumerable.Range(0, 600).Select(i => new LogEntry(t0.AddSeconds(i * 30), $"event {i}"))];

    ReadOnlySpan<LogEntry> window = LogSearch.Between(log, t0.AddMinutes(60), t0.AddMinutes(65));

    Assert.Equal(10, window.Length);
    Assert.Equal("event 120", window[0].Message);
    Assert.Equal("event 129", window[^1].Message);
}

Half-open aralık burada da işi kolaylaştırıyor: [from, to) için iki lower bound yetiyor ve ardışık pencereler ([10:00, 10:05), [10:05, 10:10)) ne çakışıyor ne de aralarında boşluk kalıyor. Sonuç bir kopya değil, orijinal array üzerinde bir ReadOnlySpan; ek bellek yok. Veritabanında aynı iş, zaman kolonundaki bir index'le yapılıyor; o index'in B-tree yapısını serinin balanced tree yazısında göreceğiz.

git bisect da aynı fikir, yalnızca sıralı array yerine commit geçmişi üzerinde: "bu commit'te bug var mı?" sorusu monotonic (iyi, iyi, ..., kötü, kötü) ve git her adımda aralığın ortasındaki commit'i test etmeni istiyor. 1.000 commit'lik bir aralıkta hatayı getiren commit'i 10 adımda buluyorsun. Kullanımı Git serisinin "Git bisect ve git worktree: Hatayı Bulan Commit ve Aynı Anda İki Branch" yazısında.

Üretimde Dikkat

Binary search'ün tek ön koşulu sıralı olmak ve bu koşulu kod denetlemiyor. Array'i sıralayan kod ile arayan kod farklı yerlerdeyse, biri değişip diğeri değişmediğinde arama sessizce yanlış cevap vermeye başlıyor. Sıralı veriyi sıralılığını garanti eden bir tipin içinde tut (SortedSet, kendi SortedPriceList class'ın) ya da en azından Debug derlemede sıralılığı Debug.Assert ile kontrol et.

Sıralama ve arama aynı comparer'ı kullanmalı. StringComparer.OrdinalIgnoreCase ile sıralanmış bir listede varsayılan comparer'la aramak, büyük/küçük harfi farklı key'leri kaçırır. Dokümandaki ifadeyle, array verilen comparer'a göre sıralı olmalı.

Binary search karşılaştırma sayısını en aza indiriyor ama bellek erişimi rastgele. Çok büyük array'lerde her adım farklı bir cache line'a, hatta farklı bir sayfaya gidiyor. Milyonlarca aramanın yapıldığı sıcak yollarda ölç; bazen bir Dictionary ya da daha küçük, cache'e sığan bir index daha hızlı.

Sık Düşülen Tuzaklar

lo = mid ile sonsuz döngü. Açılıştaki ikinci sorunun cevabı: [10, 20]'de lo = 0, hi = 1, mid = 0 ve sorted[0] <= 20 olduğu için lo = mid = 0. Hiçbir şey değişmiyor; döngü sonsuza kadar dönüyor. Test, döngüye bir adım sınırı koyarak bunu yakalıyor:

// aşağı yuvarlanan midpoint ile "lo = mid": hi == lo + 1 olunca mid == lo ve hiçbir şey değişmez
public static int LastAtMost(int[] sorted, int target, int maxSteps)
{
    int lo = 0, hi = sorted.Length - 1, steps = 0;
    while (lo < hi)
    {
        if (++steps > maxSteps) return -999; // "bu döngü hiç bitmiyor"un yerine
        int mid = lo + (hi - lo) / 2;
        if (sorted[mid] <= target) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

[Fact]
public void BuggyLastAtMost_LoEqualsMid_NeverTerminates()
{
    Assert.Equal(-999, BuggyBinarySearch.LastAtMost([10, 20], 20, maxSteps: 1_000));
}

Kural basit: lo = mid yazdıysan mid yukarı yuvarlanmalı (lo + (hi - lo + 1) / 2); daha iyisi bu yazıdaki gibi her dalda aralığı mutlaka küçülten half-open bir şablon kullanmak. "Son ≤ hedef" aslında UpperBound(target) - 1.

Sıralı olmayan veride arama. Exception yok, yalnızca yanlış cevap var:

[Fact]
public void UnsortedInput_SilentlyMissesExistingItem()
{
    int[] unsorted = [50, 10, 80, 20, 35];

    Assert.True(Array.BinarySearch(unsorted, 35) < 0); // 35 index 4'te
}

35 array'de var ama binary search ortadaki 80'e bakıp sol yarıya gidiyor ve onu hiç görmüyor. Serinin önceki yazısındaki bozuk comparer'la "sıralanmış" bir array de aynı sonucu doğurur.

Aralık tanımını karıştırmak. Kapalı aralık ([lo, hi], hi = Length - 1, while (lo <= hi)) ile half-open aralığın ([lo, hi), hi = Length, while (lo < hi)) parçalarını aynı method'da karıştırmak off-by-one hatalarının ana kaynağı. Birini seç ve bütün kod tabanında onu kullan.

Küçük Bir Deneme

★☆☆ BuggyBinarySearch.LastAtMost'u, mid'i yukarı yuvarlayarak düzelt ve aynı testi doğru cevabı (index 1) bekleyecek şekilde güncelle. Sonra aynı işi UpperBound(target) - 1 ile yap ve iki versiyonu rastgele array'lerde karşılaştır.

★★☆ Bookstore'un kitap okuma kulübü 600 sayfalık bir kitabı bölümlere ayırıp 7 güne yaymak istiyor; bölümler bölünemiyor ve sırası değişmiyor. Bir günde okunacak en fazla sayfa sayısını minimuma indiren bölüştürmeyi FirstTrue ile bul. MinCapacity ile farkı ne?

★★★ Sıralı ama döndürülmüş bir array'de (ör. [50, 80, 10, 20, 35], sıralı bir array'in bir noktadan kesilip yer değiştirmiş hâli) bir değeri O(log n)'de bulan bir method yaz. İpucu: her adımda iki yarıdan biri mutlaka sıralı.

Binary search sıralı bir array'de log n adımda arıyor ama araya eklemek O(n). Bir sonraki yazıda arama ile eklemeyi birlikte log n'de yapmaya çalışan yapıya geçiyoruz: binary search tree. Insert, find ve delete'in üç durumu, dört traversal türü ve veritabanındaki düz bir kategori tablosundan O(n)'de tree kurmak.