0Pricing
DSA Interview Prep · Ders

Klasik İkili Arama: Sol, Sağ, Orta

İkili aramayı yinelemeli ve özyinelemeli olarak uygulayın, lo/hi sınırlarındaki eksik/fazla konum ayrıntılarını doğru ele alın ve uç durum girdileriyle doğruluğu denetleyin.

Klasik İkili Arama: Sol, Sağ, Orta, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 1. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.

İkili Arama Neden Önemlidir

İkili arama, her adımda arama alanını ikiye bölerek O(n) doğrusal taramayı O(log n) düzeyine indirir. Bir milyon öğeli bir dizide doğrusal tarama 1.000.000'e kadar karşılaştırma gerektirebilirken ikili arama en fazla 20 karşılaştırma gerektirir. Bu verimlilik, onu kodlama mülakatlarında en sık sınanan algoritmalardan biri yapar.

Temel fikir şudur: sıralı bir dizi, tek bir karşılaştırmadan sonra kalan verilerin hangi yarısını tamamen eleyeceğinize karar vermenizi sağlar.

Sol, Orta, Sağ Çerçevesi

İkili arama üç dizin işaretçisi kullanır: lo (sol sınır), hi (sağ sınır) ve mid (orta nokta). Her yinelemede mid = (lo + hi) // 2 hesaplanır ve hedef, arr[mid] ile karşılaştırılır. Hedef daha küçükse hi = mid - 1 yapılır; daha büyükse lo = mid + 1 yapılır; eşitse hedef bulunmuştur.

Döngü lo <= hi olduğu sürece devam eder. Döngü hedef bulunmadan sona ererse -1 döndürün.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6))  # -1

Orta Noktada Tamsayı Taşmasını Önleme

mid = (lo + hi) // 2 ifadesi, sabit genişlikli tam sayılar kullanan dillerde (Java, C++) tamsayı taşmasına neden olabilir. Python tam sayılarında duyarlılık sınırı olmadığından taşma hiçbir zaman gerçekleşmez; ancak mülakat yapanlar yine de güvenli seçeneği bilmenizi bekler: mid = lo + (hi - lo) // 2.

Bu biçim aynı orta noktayı hesaplar; ancak önce her iki işaretçiyi toplamak yerine yalnızca yarı uzaklığı lo'ya ekler. Bir mülakatta bundan söz etmeniz, alt düzey konuların farkında olduğunuzu gösterir.

# Safe mid calculation (important in Java/C++, good habit in Python too)
lo, hi = 0, 1_000_000_000
mid_unsafe = (lo + hi) // 2   # fine in Python
mid_safe   = lo + (hi - lo) // 2  # same result, no overflow risk
print(mid_unsafe == mid_safe)  # True

Kapsayıcı ve Dışlayıcı Sınırlar

İkili aramanın en zor kısımlarından biri, hi işaretçisinin son geçerli dizini mi (kapsayıcı, hi = len(arr) - 1) yoksa dizinin sonrasındaki konumu mu (dışlayıcı, hi = len(arr)) göstereceğine karar vermektir. Farklı kurallar, farklı döngü koşulları ve sınır güncellemeleri gerektirir.

Kapsayıcı sınırlarla while lo <= hi kullanın ve hi = mid - 1 güncellemesini yapın. Dışlayıcı sınırlarla while lo < hi kullanın ve hi = mid güncellemesini yapın. Kuralları karıştırmak, ikili arama uygulamalarındaki hataların en yaygın kaynağıdır.

# Exclusive hi variant — useful for bisect-style lower-bound
def search_exclusive(arr, target):
    lo, hi = 0, len(arr)  # hi is one past last
    while lo < hi:          # strictly less than
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid         # NOT mid - 1
    return lo if lo < len(arr) and arr[lo] == target else -1

print(search_exclusive([2, 4, 6, 8, 10], 6))  # 2

Özyinelemeli İkili Arama

İkili arama, güncellenmiş lo ve hi sınırlarını çağrı yığını üzerinden aktararak özyinelemeli biçimde yazılabilir. Her özyinelemeli çağrı arama alanını yarıya indirdiğinden derinlik O(log n) olur. Temel durum, lo > hi (bulunamadı) veya arr[mid] == target (bulundu) koşuludur.

Yinelemeli sürüm, yığın çerçevesi ek yükünü ortadan kaldırdığı için üretim kodunda tercih edilir; ancak özyinelemeli sürüm, böl ve yönet yapısını beyaz tahta üzerinde daha açık biçimde anlatır.

def binary_search_rec(arr, target, lo, hi):
    if lo > hi:
        return -1
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, hi)
    else:
        return binary_search_rec(arr, target, lo, mid - 1)

arr = [1, 3, 5, 7, 9, 11]
print(binary_search_rec(arr, 9, 0, len(arr) - 1))  # 4

Sınır Durumları: Boş Dizi, Tek Öğe

Sağlam bir ikili arama, sınır durumlarını çökmeden ele almalıdır. En yaygın üç durum şunlardır: boş dizi (döngü hiç çalışmaz ve doğru biçimde -1 döndürülür), tek öğeli dizi (mid, lo ve hi'ye eşittir; tek bir karşılaştırma yeterlidir) ve aralık dışındaki hedefler (lo sonunda hi'yi aşar ve -1 döndürülür).

Mülakatta devam sorularına geçmeden önce uygulamanızı her zaman bu girdilerle doğrulayın.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([], 5))       # -1  (empty)
print(binary_search([7], 7))      # 0   (single, found)
print(binary_search([7], 3))      # -1  (single, not found)
print(binary_search([1,3,5], 0))  # -1  (below range)
print(binary_search([1,3,5], 9))  # -1  (above range)

Zaman ve Alan Karmaşıklığı

İkili aramanın zaman karmaşıklığı O(log n)'dir; çünkü her karşılaştırma arama alanını ikiye böler. k karşılaştırmadan sonra kalan alan n/2^k olur; arama bu değer 1'e ulaştığında sona erer, dolayısıyla k = log₂ n'dir.

Alan karmaşıklığı, yinelemeli sürümde (yalnızca üç tamsayı değişken kullanıldığı için) O(1), özyinelemeli sürümde ise çağrı yığını derinliği nedeniyle O(log n)'dir. Mülakatta her ikisini de belirtin ve alan kısıtlıysa yinelemeli biçimi tercih edin.

import math

for n in [10, 100, 1000, 1_000_000, 1_000_000_000]:
    steps = math.ceil(math.log2(n + 1))
    print(f'n={n:>12,}  max comparisons={steps}')

Tam Eşleşme mi, Sınır mı Aranıyor

Klasik ikili arama, hedefin bulunduğu herhangi bir dizini döndürür. Ancak birçok mülakat sorusu hedefin ilk veya son görülmesini ister. Bu durumlarda bir eşleşme bulduktan sonra aramaya devam etmeniz gerekir; hemen döndürmek yerine sınırı daraltıp aramayı sürdürün.

İlk görülmeyi ararken arr[mid] == target bulduktan sonra mid değerini aday olarak kaydedin ve hi = mid - 1 yapın. Son görülme için lo = mid + 1 yapın.

def first_occurrence(arr, target):
    lo, hi, result = 0, len(arr) - 1, -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            result = mid
            hi = mid - 1   # keep searching left
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result

print(first_occurrence([1, 2, 2, 2, 3], 2))  # 1

Python'ın bisect Modülünü Kullanma

Python'ın standart kitaplığı, üretim kullanımına hazır ikili arama için bisect.bisect_left(arr, x) ve bisect.bisect_right(arr, x) işlevlerini sağlar. bisect_left, dizinin sıralı kalmasını sağlayacak şekilde x'in eklenebileceği en soldaki dizini döndürür; başka bir deyişle arr[i] >= x koşulunu sağlayan ilk konumu bulur.

Mülakat yapanlar bisect kullanmanıza izin verebilir; önce mutlaka onay alın. Nasıl çalıştığını (O(log n) süreli ikili arama olduğunu) iç düzeyde bilmek yine de çok önemlidir.

import bisect

arr = [1, 2, 2, 2, 3, 5]

print(bisect.bisect_left(arr, 2))   # 1  (first 2)
print(bisect.bisect_right(arr, 2))  # 4  (after last 2)

# Check if target exists
target = 3
idx = bisect.bisect_left(arr, target)
print(idx < len(arr) and arr[idx] == target)  # True

Yaygın İkili Arama Tuzakları

Mülakatlarda ikili arama hatalarının çoğuna üç hata neden olur. Birincisi, yanlış döngü koşulu: kapsayıcı sınırlarla < yerine <= kullanmak, geriye kalan son öğenin atlanmasına neden olur. İkincisi, hatalı sınır güncellemesi: +1 veya -1 eklemeyi unutmak, lo == hi olduğunda sonsuz döngü oluşturur. Üçüncüsü, sıralanmamış bir dizi üzerinde işlem yapmak: ikili arama yalnızca sıralı verilerde doğrudur.

Herhangi bir ikili arama yazmadan önce şunu sesli olarak belirtin: “Dizi sıralı, sınırlarım kapsayıcı ve döngüm lo <= hi olduğu sürece çalışıyor.”

# BUG: infinite loop when lo == hi because hi = mid never moves past lo
def buggy(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:              # should be lo <= hi for exact-match
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid            # stops, but never returns mid when found
    return lo if arr[lo] == target else -1

print(buggy([1, 3, 5, 7], 7))  # 3 (works here by luck)
print(buggy([1, 3, 5, 7], 1))  # 0 (correct)
print(buggy([1, 3, 5, 7], 4))  # -1 (correct)

İkili Arama İçin Mülakat İpuçları

Sıralı bir dizi, monoton artan bir işlev veya ikiye bölünebilen bir arama alanı gördüğünüzde hemen ikili aramayı değerlendirin. Mülakatta düşüncenizi sesli ifade edin: “Dizi sıralı olduğundan her karşılaştırmada öğelerin yarısını eleyebilirim; bu da O(log n) süre sağlar.”

Çözümünüzü her zaman en az üç girdide doğrulayın: başlangıçtaki bir değer, sondaki bir değer ve bulunmayan bir değer. Karmaşıklığı önceden belirtmek — “zaman O(log n), alan O(1)” — sorulmasını beklemeden temel bilgilerinizin güçlü olduğunu gösterir.

Hızlı Kontrol

Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını anlayışınızı sınayın.

Ders Özeti

Bu derste şunları öğrendiniz: ikili arama, O(log n) zamanla her adımda arama alanını ikiye böler, kapsayıcı sınır kuralında lo <= hi kullanılır ve lo = mid+1 ile hi = mid-1 güncellenir ve ilk/son görülmeleri bulmak için bir eşleşmeden sonra hemen dönmek yerine aramayı sürdürürsünüz. Sırada ikili aramanın döndürülmüş ve sıralanmamış dizilere nasıl genişletildiğini inceleyeceğiz.

Sıkça Sorulan Sorular

“Klasik İkili Arama: Sol, Sağ, Orta” dersi ücretsiz mi?

Evet — “Klasik İkili Arama: Sol, Sağ, Orta” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.

“Klasik İkili Arama: Sol, Sağ, Orta” dersinde ne öğreneceğim?

İkili aramayı yinelemeli ve özyinelemeli olarak uygulayın, lo/hi sınırlarındaki eksik/fazla konum ayrıntılarını doğru ele alın ve uç durum girdileriyle doğruluğu denetleyin. DSA Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.

DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 1. dersidir.

“Klasik İkili Arama: Sol, Sağ, Orta” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Bu kursun tüm dersleri

  1. Klasik İkili Arama: Sol, Sağ, Orta
  2. Döndürülmüş ve Sıralanmamış Dizilerde İkili Arama
  3. Alt Sınır ve Üst Sınır
  4. Yanıt Uzayında İkili Arama
← DSA Interview Prep Sayfasına Dön