Kalıp #05
Cevap Üzerinde İkili Arama
TemelCevap değerinin kendisinde ikili ara; adayın uygulanabilirliğini doğrusal zamanda kontrol et.
Ne zaman kullanılır
Greedy veya tarama ile doğrulanabilen bir X için min/maks arıyorsan. Kapasite, hız ve bölme problemlerinde klasik.
Tanıma ipuçları
- Maksimumu minimize et / minimumu maksimize et
- Koko muz yeme, paket taşıma, dizi en büyük toplamını böl
- Uygulanabilirlik kontrolü O(n) ve tahmin cevaba göre monoton
Yaygın tuzaklar
- Yanlış arama sınırları (lo/hi çok dar veya çok geniş)
- Aslında monoton olmayan uygulanabilirlik
- mid veya oranlarda tamsayı bölme
90 saniyelik tanıma egzersizi
Hangisi en iyi uyuyor?
- Maksimumu minimize et / minimumu maksimize et
- Koko muz yeme, paket taşıma, dizi en büyük toplamını böl
- Uygulanabilirlik kontrolü O(n) ve tahmin cevaba göre monoton
Interactive
Zihinsel model
Değişmezin tam adım adım anlatımı. Duraklat, noktalara tıkla veya ← → kullan. Her adımı kendi cümlelerinle anlatmayı hedefle.
feasible(x) is monotonic
Search the answer domain, not array indices. Example: min feasible speed.
Nasıl düşünülür
Dizi indeksi aramıyorsun. Cevap uzayında [lo, hi] arıyorsun. mid tahmini için feasible(mid) çalıştır. Uygulanabilirlik monoton olduğu için ikili arama ilk true (min) veya son true (maks) bulur.
Tarif
- Monotonluğu kanıtla:
Xişe yarıyorsa daha büyük (veya küçük) de yarıyor. lo/hiiçin sıkı geçerli sınırlar koy.- Doğru bir
feasibleyaz. - İlk true (min) veya son true (maks) için ikili ara.
Karmaşıklık temeli
O(n log R) - R cevap aralığının boyutu.
Şablon
TypeScript, Python ve C#’te aynı iskelet. Değişmezi uyarla; yapıyı koru.
/** Binary search on answer: first mid where feasible(mid) is true. */
export function binarySearchOnAnswer(
lo: number,
hi: number,
feasible: (mid: number) => boolean,
): number {
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (feasible(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
/** Binary search on answer: first mid where feasible(mid) is true. */
export function binarySearchOnAnswer(
lo: number,
hi: number,
feasible: (mid: number) => boolean,
): number {
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (feasible(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
- 1#410 Split Array Largest SumRehberhard
- 2#774 Minimize Max Distance to Gas StationRehberhard
- 3#875 Koko Eating BananasRehbermedium
- 4#1011 Capacity To Ship Packages Within D DaysRehbermedium
- 5#1283 Find the Smallest Divisor Given a ThresholdRehbermedium
- 6#1482 Minimum Number of Days to Make m BouquetsRehbermedium