Yanıt Uzayında İkili Arama
Sürekli bir yanıt aralığını arama uzayı olarak ele alıp işleri tamamlama süresi minimumu ve paket gönderme kapasitesi gibi problemleri çözün.
Yanıt Uzayında İkili Arama, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 4. 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, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Yanıt Uzayında İkili Arama
Çoğu kişi sıralı bir dizide değer bulmak için ikili aramayı bilir. Ancak ikili arama, olası yanıtlar uzayına uygulandığında çok daha güçlüdür. Bir dizide arama yapmak yerine sayısal bir aralıkta arama yaparsınız — örneğin, “tüm paketleri göndermek için gereken en az gün sayısı nedir?” — ve bir kontrol işlevi kullanarak aday bir yanıtın uygun olup olmadığına karar verirsiniz.
Bu teknik, birçok eniyileme problemini O(n²) veya daha kötüsünden O(n log(max_answer)) düzeyine dönüştürür.
Yanıt Uzayı Şablonu
Şablonun üç bileşeni vardır. İlk olarak, tüm geçerli yanıtları kapsayan arama aralığını [lo, hi] tanımlayın. İkinci olarak, mid değerine ulaşılabiliyorsa True döndüren bir uygunluk kontrolü can_achieve(mid) yazın. Üçüncü olarak, [lo, hi] üzerinde ikili arama yapın: can_achieve(mid) doğruysa daha küçük (veya daha büyük) bir yanıta doğru ilerleyin; aksi hâlde diğer yönde ilerleyin.
Temel özellik şudur: uygunluk işlevi monoton olmalıdır — bir yanıt uygun hâle geldikten sonra, ötesindeki tüm değerler de uygun olmalıdır (veya altındaki tüm değerler uygun olmamalıdır).
# Generic template
def answer_space_search(lo, hi, is_feasible):
result = hi # or lo, depending on direction
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
hi = mid - 1 # try to minimise further
else:
lo = mid + 1
return resultÖrnek: Paket Gönderme Kapasitesi
LeetCode 1011 'D Gün İçinde Paket Gönderme Kapasitesi': Ağırlık listesi ve D gün verildiğinde, tüm paketleri sırayla D gün içinde göndermek için gereken minimum gönderim kapasitesini bulun. Cevap [max(weights), sum(weights)] aralığındadır. Açgözlü bir benzetim tüm paketleri D gün içinde göndermeye yetiyorsa kapasite uygulanabilirdir. Kapasite aralığında ikili arama yapmak, O(n log(sum)) zamanında sonuç verir.
def shipWithinDays(weights, days):
def can_ship(capacity):
needed_days, current_load = 1, 0
for w in weights:
if current_load + w > capacity:
needed_days += 1
current_load = 0
current_load += w
return needed_days <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_ship(mid):
hi = mid # feasible, try smaller
else:
lo = mid + 1 # not feasible, need more capacity
return lo
print(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5)) # 15
print(shipWithinDays([3,2,2,4,1,4], 3)) # 6Örnek: Koko'nun Muz Yemesi
LeetCode 875 'Koko Muz Yiyor': Koko saatte K muz yiyebilir; H muz yığınını tam olarak H saatte bitirmek ve K'yi en aza indirmek ister. Arama aralığı [1, max(piles)] şeklindedir. Kontrol şu şekildedir: K hızında toplam saat sayısı = sum(ceil(pile/K)) olur ve bu değer <= H olmalıdır. Bu koşulu sağlayan en küçük K'yi bulmak için ikili arama yaparız.
import math
def minEatingSpeed(piles, h):
def can_finish(k):
return sum(math.ceil(p / k) for p in piles) <= h
lo, hi = 1, max(piles)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_finish(mid):
hi = mid # feasible, try lower speed
else:
lo = mid + 1 # too slow
return lo
print(minEatingSpeed([3,6,7,11], 8)) # 4
print(minEatingSpeed([30,11,23,4,20], 5)) # 30Buketi Oluşturmak İçin Minimum Gün Sayısı
LeetCode 1482 'm Buket Oluşturmak İçin Minimum Gün Sayısı': Her biri k bitişik açmış çiçekten oluşan m bukete ihtiyacınız vardır. i. çiçek bloomDay[i] gününde açar. Gün sayısı üzerinde ikili arama yapın: aralık [1, max(bloomDay)] şeklindedir. Uygulanabilirlik kontrolü, art arda açmış çiçekleri sayar ve m buketin oluşturulup oluşturulamayacağını kontrol eder. Monotonluk özelliği şudur: d günü işe yarıyorsa, d+1 günü de işe yarar.
def minDays(bloomDay, m, k):
if m * k > len(bloomDay):
return -1 # impossible
def can_make(day):
bouquets = consecutive = 0
for bd in bloomDay:
if bd <= day:
consecutive += 1
if consecutive == k:
bouquets += 1
consecutive = 0
else:
consecutive = 0
return bouquets >= m
lo, hi = 1, max(bloomDay)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_make(mid):
hi = mid
else:
lo = mid + 1
return lo
print(minDays([1,10,3,10,2], 3, 1)) # 3
print(minDays([1,10,3,10,2], 3, 2)) # -1Arama Aralığını Belirleme
Doğru [lo, hi] aralığını seçmek kritik önem taşır. lo, mümkün olan en küçük sonuç olmalıdır (örneğin en küçük öğe, 1 veya 0) ve hi, mümkün olan en büyük sonuç olmalıdır (örneğin tüm öğelerin toplamı, en büyük öğe veya n). hi değerini çok küçük belirlemek geçerli sonuçların gözden kaçmasına neden olur; çok büyük belirlemek ise sorun değildir, çünkü ikili arama yine de O(log(hi - lo)) adımda yakınsar.
# Choosing lo and hi for common problems:
# Capacity to ship: lo=max(weights), hi=sum(weights)
# Koko eating: lo=1, hi=max(piles)
# Square root: lo=1, hi=x
# Allocate books: lo=max(pages), hi=sum(pages)
def isqrt_bs(x):
if x < 2:
return x
lo, hi = 1, x
while lo < hi:
mid = lo + (hi - lo) // 2
if mid * mid <= x:
lo = mid + 1
else:
hi = mid
return lo - 1
for n in [0, 1, 4, 8, 9, 15, 16]:
print(f'isqrt({n}) = {isqrt_bs(n)}')En Küçük ve En Büyük Değeri Bulma: Yön Önemlidir
Cevap uzayında ikili aramanın iki çeşidi vardır. Cevabı en küçükleme: kontrol başarılı olduğunda daha küçük değerleri deneyin (hi = mid); başarısız olduğunda daha büyük değerleri deneyin (lo = mid + 1). Cevabı en büyükleme: kontrol başarılı olduğunda daha büyük değerleri deneyin (lo = mid + 1, mid'i aday olarak kaydederek); başarısız olduğunda daha küçük değerleri deneyin (hi = mid - 1). Kodlamaya başlamadan önce hangi yönde arama yaptığınızı her zaman netleştirin.
# Maximise: largest x such that f(x) is feasible
def max_feasible(lo, hi, is_feasible):
result = lo - 1 # sentinel: no feasible answer found
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
lo = mid + 1 # try larger
else:
hi = mid - 1
return result
# Example: largest k such that k^2 <= 50
print(max_feasible(1, 50, lambda k: k * k <= 50)) # 7Minimum Sayfa Ayırma (Klasik Problem)
pages[] dizisindeki n kitap ve k öğrenci verildiğinde, kitapları bitişik olacak şekilde dağıtın; böylece en fazla sayfa okuyan öğrencinin okuduğu sayfa sayısı mümkün olduğunca az olsun. Cevap (mümkün olan en küçük maksimum) üzerinde ikili arama yapın. Uygulanabilirlik kontrolü kitapları öğrencilere açgözlü biçimde atar: bir kitap eklendiğinde mevcut maksimumu aşacaksa kitabı yeni bir öğrenciye verin. Gereken öğrenci sayısı <= k ise bu maksimuma ulaşılabilir.
def allocate_min_pages(pages, k):
if k > len(pages):
return -1
def is_feasible(max_pages):
students, current = 1, 0
for p in pages:
if p > max_pages:
return False # single book exceeds limit
if current + p > max_pages:
students += 1
current = 0
current += p
return students <= k
lo, hi = max(pages), sum(pages)
while lo < hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
print(allocate_min_pages([12, 34, 67, 90], 2)) # 113
print(allocate_min_pages([10, 20, 30, 40], 2)) # 60Cevap Uzayı Aramasının Karmaşıklık Analizi
Zaman karmaşıklığı, n'nin uygulanabilirlik kontrolünün maliyeti (genellikle doğrusal bir tarama) ve range = hi - lo'nun cevap uzayının boyutu olduğu durumda O(n × log(range)) şeklindedir. Örneğin sayfaların toplamı 10⁹ ve uygulanabilirlik kontrolü O(n) ise toplam zaman O(n log 10⁹) ≈ O(30n) olur; bu, O(n²) kaba kuvvet yaklaşımından çok daha iyidir.
Alan karmaşıklığı, ikili aramanın kendisi için O(1) ve uygulanabilirlik kontrolünün kullandığı ek alan kadardır.
import math
# Compare brute force vs answer-space binary search
# For sum = 10^9 and n = 10^5:
brute_ops = 10**9 # try every possible answer
bsearch_ops = 10**5 * math.log2(10**9) # n * log(range)
print(f'Brute force: {brute_ops:,.0f} operations')
print(f'Binary search: {bsearch_ops:,.0f} operations')
print(f'Speedup: {brute_ops / bsearch_ops:,.0f}x')Sıralı Matristeki K'ıncı En Küçük Öğe
LeetCode 378 'Sıralı Matristeki K'ıncı En Küçük Öğe': n×n matrisin her satırı ve sütunu sıralıdır. Cevap değeri üzerinde [matrix[0][0], matrix[n-1][n-1]] aralığında ikili arama yapın. Uygulanabilirlik kontrolü, sol alt köşeden başlayan bir işaretçi kullanarak <= mid olan öğeleri O(n) zamanda sayar. En az k öğenin <= mid olduğu en küçük değeri bulun.
def kthSmallest(matrix, k):
n = len(matrix)
def count_le(mid):
count, row, col = 0, n - 1, 0
while row >= 0 and col < n:
if matrix[row][col] <= mid:
count += row + 1
col += 1
else:
row -= 1
return count
lo, hi = matrix[0][0], matrix[n-1][n-1]
while lo < hi:
mid = lo + (hi - lo) // 2
if count_le(mid) >= k:
hi = mid
else:
lo = mid + 1
return lo
matrix = [[1,5,9],[10,11,13],[12,13,15]]
print(kthSmallest(matrix, 8)) # 13Cevap Uzayı Problemlerini Tanıma
Cevap uzayında ikili aramaya uygun problemler bazı ortak işaretler taşır: soru bir en küçük veya en büyük değeri ister, cevap sınırlı bir sayısal aralıkta bulunur ve aday cevabı artırmak (veya azaltmak), uygulanabilirliği monoton olarak daha iyi ya da daha kötü hale getirir. Klasik anahtar ifadeler arasında 'mümkün olan en küçük maksimum', 'en fazla k işlem' ve 'd gün içinde' bulunur.
Bu işaretleri fark ettiğinizde lo ve hi'yi hemen tanımlayın, uygulanabilirlik işlevini yazın ve şablonu uygulayın. Bu yapılandırılmış yaklaşım, mülakatlarda nadiren başarısız olur.
Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını anlayıp anlamadığınızı test edin.
Ders Özeti
Bu derste şunları öğrendiniz: uygulanabilirlik işlevi sayısal bir aralıkta monoton olduğunda cevap uzayında ikili arama uygulanır, şablon [lo, hi] aralığında arama yapar ve arama uzayını yarıya indirmek için bir can_achieve kontrolü kullanır ve toplam karmaşıklık, tek bir uygulanabilirlik kontrolünün maliyeti n olmak üzere O(n log(range)) şeklindedir. Sıradaki konuda bağlantılı listelere ve Node sınıfına geçiyoruz.
Sıkça Sorulan Sorular
“Yanıt Uzayında İkili Arama” dersi ücretsiz mi?
Evet — “Yanıt Uzayında İkili Arama” 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 Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Yanıt Uzayında İkili Arama” dersinde ne öğreneceğim?
Sürekli bir yanıt aralığını arama uzayı olarak ele alıp işleri tamamlama süresi minimumu ve paket gönderme kapasitesi gibi problemleri çözün. Coding 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.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding 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 4. dersidir.
“Yanıt Uzayında İkili Arama” 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 Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding 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
- Klasik İkili Arama: Sol, Sağ, Orta
- Döndürülmüş ve Sıralanmamış Dizilerde İkili Arama
- Alt Sınır ve Üst Sınır
- Yanıt Uzayında İkili Arama