İlk True: Predicate İkili Araması
Tekdüze bir evet/hayır sınırını arayın.
İlk True: Predicate İkili Araması, CoddyKit'te ücretsiz bir Competitive Programming Academy dersidir. Bu, 4 dersinin 3. 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, Competitive Programming Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
Evet-Hayır Sınırını Arayın
Birçok problemde monoton bir yüklem gizlidir: false, false ve ardından sonsuza kadar true. İkili arama, sıralı bir dizi olmadan bu ilk true değerini bulabilir.
# FFFFTTTT -> find first TMonoton Ne Demektir
Bir yüklem, true olduktan sonra true kalıyorsa monotondur. Sınırı ikili arayabilmenizi sağlayan tek özellik budur.
def ok(x):
return x * x >= targetYanıt Alanını Belirleyin
Sınırı kesinlikle içeren bir aralık seçin. low değerini en küçük adaya, high değerini ise ok değerinin kesinlikle true olduğu bir değere ayarlayın.
low, high = 0, 10**9Ortayı Test Edin
mid değerini alın ve ok(mid) çağrısını yapın. Boolean sonucu, sıradan ikili aramada bir değeri karşılaştırmaya benzer şekilde hangi yarıyı koruyacağınızı söyler.
mid = (low + high) // 2
if ok(mid):
...True Daha Küçük Olabileceği Anlamına Gelir
ok(mid) true ise mid geçerli bir yanıttır, ancak daha küçük bir yanıt da işe yarayabilir. high = mid yaparak mid değerini koruyun; mid - 1 yapmayın.
if ok(mid):
high = midFalse Daha Yükseğe Gitmek Demektir
ok(mid) false ise sınır mid değerinin üzerindedir. low = mid + 1 ile mid'i ve altındaki her şeyi eleyin.
else:
low = mid + 1Low High'dan Küçük Olduğu Sürece Döngü
while low < high kullanın; küçük veya eşit koşulunu kullanmayın. İki işaretçi ilk true indeksine yakınsar ve ardından döngü durur.
while low < high:
mid = (low + high) // 2Yanıt Low Değeridir
Döngü sona erdiğinde low, high değerine eşittir ve ikisi de ilk true değerini gösterir. Aradığınız sınır olarak low değerini döndürün.
return low # first x where ok(x)high = mid Neden Çalışır
mid yanıt olabileceği için onu atlamamalısınız. high = mid kullanmak, aralığı küçültürken mid değerini aralıkta tutar ve ilerlemeyi garanti eder.
high = mid # mid stays a candidateTam Sayı Karekökü Örneği
x*x değeri n'den küçük veya n'ye eşit olan en büyük x'i bulmak için x*x > n koşulunun ilk true değerini arayın, ardından bir adım geri gidin. Bu kalıp kendi kendini yeniden kullanır.
def ok(x):
return x * x > n
# answer is found_index - 1Tek Şablon, Birçok Problem
Bu ilk-true şablonu sayısız görevi çözer: mümkün olan en küçük değer, en soldaki indeks, en küçük kapasite. Bir kez öğrenin, her yerde yeniden kullanın.
# low<high, ok->high=mid, else low=mid+1Hızlı Kontrol
Adayı geçerli tutan hamleyi netleştirin.
Özet: İlk True Bulundu
Artık bir problemi monoton bir yükleme dönüştürebilir ve sınırı ikili arayabilirsiniz. high = mid ile while low < high, güvenli kalıptır. 🧭
Sıkça Sorulan Sorular
“İlk True: Predicate İkili Araması” dersi ücretsiz mi?
Evet — “İlk True: Predicate İkili Araması” 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 Competitive Programming Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
“İlk True: Predicate İkili Araması” dersinde ne öğreneceğim?
Tekdüze bir evet/hayır sınırını arayın. Competitive Programming Academy 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.
Competitive Programming Academy öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Competitive Programming Academy, 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 3. dersidir.
“İlk True: Predicate İkili Araması” 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 Competitive Programming Academy dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Competitive Programming Academy 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
- Hatasız Klasik İkili Arama
- bisect_left ve bisect_right
- İlk True: Predicate İkili Araması
- Yanıt Üzerinde İkili Arama