Javob ustida binary search: minimal sig'im, tezlik va taqsimlash masalalari

Qisqacha: Ba'zan massivda emas, javobning o'zida qidiramiz. "Eng kichik sumka sig'imi qancha bo'lsa, buyurtmalar 3 kunda yetkaziladi?" — javob 9 dan 44 gacha bo'lgan son. Har sig'im uchun "yetadimi?" ni O(n) da tekshirish oson, savol esa monoton: bir sig'im yetsa, kattarog'i ham yetadi. Demak, birinchi "ha" ni binar qidiruv bilan topamiz — O(n · log S), bu yerda S — javoblar oralig'i. Hamma sig'imni bittalab sinash esa O(n · S).

Bu darsda

• Masalada monoton predikatni ko'rib, "javob ustida binar qidiruv" qo'llash mumkinligini aniqlaysiz.
• Javobning pastki va yuqori chegarasini to'g'ri tanlaysiz.
• Minimal sig'im, minimal tezlik va taqsimlash masalalarini bitta shablon bilan yechasiz.
• Sodda O(n · S) va tez O(n log S) yechimni o'lchov bilan solishtirasiz.

Oldin bilishingiz kerak: Binary search variantlari, Binary search asoslari.

1. Nega bu kerak?

«Bahor» yetkazish xizmati ochdi. Kuryer Sardor bitta sumka bilan ishlaydi. Bugungi buyurtmalar og'irligi (kg) — [5, 8, 3, 7, 6, 4, 9, 2]. Ular qat'iy shu tartibda yetkazilishi kerak: kim oldin buyurtma bergan bo'lsa, o'sha oldin oladi. Har kuni sumkaga sig'guncha buyurtma olinadi, sig'maganini ertaga.

Jasur aka sumka sotib olmoqchi. "Hammasi 3 kunda yetkazilsin. Eng kichik qanday sumka yetadi? Kattasi qimmat." Sardorning birinchi fikri: 9 kg dan (eng og'ir buyurtma) boshlab, har sig'imni sinab ko'rish. 9 — yetmaydi, 10 — yetmaydi, … 16 — yetadi!

Ishlaydi. Lekin buyurtmalar 100 000 ta bo'lsa-chi? Javob minglab kilogramm bo'ladi va har sinov 100 000 buyurtmani yuradi.

Asosiy murakkablik sinflari darsidagi menyu o'yinini eslang. Jasur aka taom o'ylardi, Sardor esa sahifa ochib, "oldinroq" yoki "keyinroq" degan javob olardi. Bugun ham o'yin xuddi shunday, faqat menyu kitobi yo'q. Sardor sig'imni aytadi: "26 kg?" Javob — "yetadi" yoki "yetmaydi". Har javob nomzodlarning yarmini o'chiradi.

Binary search variantlari darsidagi «Umumiy shakl» bo'limida firstTrue ni yozgan edik — u massivda emas, sonlar oralig'ida ishlardi. Bugun shundan foydalanamiz.

2. Ikkita kichik savol

2.1 Tekshiruv: shu sig'im yetadimi?

"Eng kichik sig'im qancha?" — qiyin savol. "16 kg yetadimi?" — oson savol. Buyurtmalarni tartib bilan yuramiz, sig'guncha bugungi kunga qo'shamiz, sig'masa — yangi kun:

function daysNeeded(weights, capacity) {
  let days = 1;
  let load = 0;
  for (const w of weights) {
    if (load + w > capacity) { // sig'maydi — ertaga
      days++;
      load = 0;
    }
    load += w;
  }
  return days;
}

const weights = [5, 8, 3, 7, 6, 4, 9, 2];
console.log(daysNeeded(weights, 16)); // 3
console.log(daysNeeded(weights, 15)); // 4
console.log(daysNeeded(weights, 44)); // 1

Bu — greedy (ochko'z) usul: har kuni imkon qadar ko'p yuklash. Bu yerda u to'g'ri: buyurtmani "ertaga qoldirish" hech qachon kunlarni kamaytirmaydi. Greedy algoritmlarni alohida darsda chuqur o'rganamiz. Narxi — O(n).

2.2 Monotonlik

Endi asosiy kuzatuv. Sig'imni oshirsak, kunlar soni kamayadi yoki o'zgarmaydi — hech qachon oshmaydi. Kattaroq sumkaga kichik sumkaga sig'gan hamma narsa sig'adi. Demak, "3 kunda yetadimi?" savoli sig'im bo'yicha monoton:

sig'im:  9  10  11  12  13  14  15  16  17  18 ... 44
kunlar:  6   5   5   4   4   4   4   3   3   3 ...  1
≤ 3?     –   –   –   –   –   –   –   ✓   ✓   ✓ ...  ✓

Bu jadval o'tgan darsdagi ≥ 19? qatorining aynan o'zi: avval faqat "yo'q", keyin faqat "ha". Massiv yo'q — lekin "ha"lar boshlanadigan chegara bor. Uni binar qidiruv topadi.

Bunday savol — monoton predikat (monotonic predicate): argument o'sgan sari javobi faqat bir marta, "yo'q" dan "ha" ga almashadigan funksiya.

Tekshirib ko'ring: "Shu sig'im bilan kunlar soni aynan 3 bo'ladimi?" degan savol monotonmi?

3. Javob ustida binar qidiruv

3.1 Chegaralar

Binar qidiruvga oraliq kerak: javob qayerdan qayergacha bo'lishi mumkin?

• Pastki chegara lo: eng og'ir buyurtma — 9 kg. Undan kichik sumkaga u umuman sig'maydi, demak bundan kichik javob bo'lishi mumkin emas.
• Yuqori chegara hi: hamma buyurtmalar yig'indisi — 44 kg. Bunday sumka bilan hammasi bir kunda ketadi, demak 44 doim yetadi.

Chegaralar to'g'ri bo'lishi shart: hi albatta "ha" bo'lsin, lo dan pastda "ha" bo'lmasin. Shunda javob doim [lo, hi] ichida.

3.2 Qidiruv

O'tgan darsdagi yarim ochiq shakl: mid yetsa — hi = mid (javob mid yoki undan kichik), yetmasa — lo = mid + 1:

36 ta nomzoddan 5 tasini tekshirdik. Har tekshiruv — daysNeeded, O(n).

3.3 Kod

function daysNeeded(weights, capacity) {
  let days = 1;
  let load = 0;
  for (const w of weights) {
    if (load + w > capacity) {
      days++;
      load = 0;
    }
    load += w;
  }
  return days;
}

function minCapacity(weights, maxDays) {
  let lo = 0; // eng og'ir buyurtma
  let hi = 0; // hammasi bir kunda
  for (const w of weights) {
    lo = Math.max(lo, w);
    hi += w;
  }
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (daysNeeded(weights, mid) <= maxDays) hi = mid; // yetadi
    else lo = mid + 1; // yetmaydi
  }
  return lo;
}

const weights = [5, 8, 3, 7, 6, 4, 9, 2];
console.log(minCapacity(weights, 3)); // 16
console.log(minCapacity(weights, 8)); // 9 — har kuni bittadan
console.log(minCapacity(weights, 1)); // 44 — hammasi bir kunda

Chegaralarni nega Math.max(...weights) bilan emas, sikl bilan hisobladik? Buni «Ko'p uchraydigan xatolar» bo'limida ko'ramiz — u katta massivda yiqiladi.

3.4 Murakkablik

S = hi − lo — javoblar oralig'ining kengligi. Binar qidiruv log₂ S ta tekshiruv qiladi, har tekshiruv O(n). Jami O(n · log S). Qo'shimcha xotira — O(1).

Sodda yechim — lo dan boshlab bittalab sinash:

function daysNeeded(weights, capacity) {
  let days = 1;
  let load = 0;
  for (const w of weights) {
    if (load + w > capacity) {
      days++;
      load = 0;
    }
    load += w;
  }
  return days;
}

// sodda yechim: eng og'ir buyurtmadan boshlab bittalab sinaymiz
function minCapacitySlow(weights, maxDays) {
  let capacity = Math.max(...weights);
  let checks = 1;
  while (daysNeeded(weights, capacity) > maxDays) {
    capacity++;
    checks++;
  }
  return { capacity, checks };
}

const weights = [5, 8, 3, 7, 6, 4, 9, 2];
console.log(minCapacitySlow(weights, 3));
console.log(minCapacitySlow(weights, 1));

Konsolda:

{ capacity: 16, checks: 8 }
{ capacity: 44, checks: 36 }

Eng yomon holatda S ta tekshiruv — O(n · S). 8 ta buyurtmada farq kichik (8 ga qarshi 5). Lekin S buyurtmalar soniga qarab o'sadi: 100 000 ta buyurtmada yig'indi milliondan oshadi.

4. O'lchov: n ikki baravar oshsa

Og'irliklar 1–20 kg (urug'li), 10 kunda yetkazish. Performansni o'lchash darsidagi usul bilan o'lchadik: har n alohida jarayonda, avval isitish, 7 o'lchovning medianasi:

Nega bittalab sinash to'rt baravar sekinlashdi, garchi formulada n faqat bir marta bor? Chunki S ham n bilan birga o'sdi: 10 kunda yetkazish uchun sig'im taxminan yig'indi ÷ 10, yig'indi esa n ga proporsional. n ×2 → S ×2 → n · S ×4. Binar qidiruvda esa log S atigi bittaga oshadi — vaqt taxminan ikki baravar. 8 000 buyurtmada bittalab sinash ≈ 0,5 s, binar qidiruv esa 800 000 buyurtmani ≈ 0,15 s da hal qiladi.

Tekshirib ko'ring: Buyurtmalar soni o'zgarmadi, lekin har biri 1 000 baravar og'irlashdi (kilogramm o'rniga gramm yozildi). Binar qidiruvdagi tekshiruvlar soni qanday o'zgaradi?

5. Ikkinchi masala: oshpazning tezligi

5.1 Masala

Oshxonada 5 ta qozonda manti partiyalari bor: [30, 11, 23, 4, 20] dona. Oshpaz soatiga k dona manti tugadi. Har soat u faqat bitta qozon bilan ishlaydi: qozonda k dan kam qolsa, qolganini tugadi va soatning qolgan qismida dam oladi. Jasur aka: "8 soatda hammasi tayyor bo'lsin. Eng sekin qanday tezlik yetadi?"

Bu — LeetCode'dagi mashhur 875 "Koko Eating Bananas" masalasining «Bahor» varianti (u yerda maymun banan yeydi).

5.2 Uch savol — uch javob

1. Tekshiruv: k tezlikda necha soat ketadi? Har qozonga Math.ceil(b / k) soat — yuqoriga yaxlitlash, chunki chala soat ham soat. Jami — O(n).
2. Monotonlik: tezlik oshsa, soatlar kamayadi yoki o'zgarmaydi. "≤ 8 soatmi?" — monoton.
3. Chegaralar: lo = 1 (soatiga kamida bitta), hi = eng katta qozon — bunday tezlikda har qozon bir soatda tugaydi, n soat yetadi.

Kodga o'tishdan oldin bitta tekshiruvni qo'lda bajaramiz. Tezlik 15 dona/soat bo'lsin:

• 30 donali qozon — 2 soat;
• 11 dona — 1 soat (15 dan kam, lekin baribir bir soat);
• 23 dona — 2 soat, 4 dona — 1 soat, 20 dona — 2 soat.

Jami 2 + 1 + 2 + 1 + 2 = 8 soat — yetadi. Tezlik 14 bo'lsa-chi? Unda 30 donali qozon 3 soat oladi (14 + 14 + 2), jami 9 soat — yetmaydi.

// [lo, hi] oralig'ida isGood rost bo'ladigan eng kichik son
function firstTrue(lo, hi, isGood) {
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (isGood(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

function hoursNeeded(batches, speed) {
  let hours = 0;
  for (const b of batches) hours += Math.ceil(b / speed);
  return hours;
}

function minSpeed(batches, maxHours) {
  let biggest = 1;
  for (const b of batches) biggest = Math.max(biggest, b);
  const enough = (k) => hoursNeeded(batches, k) <= maxHours;
  return firstTrue(1, biggest, enough);
}

const batches = [30, 11, 23, 4, 20];
console.log(minSpeed(batches, 8)); // 15
console.log(hoursNeeded(batches, 15)); // 8
console.log(hoursNeeded(batches, 14)); // 9

Javob — 15 dona/soat. Tekshiruv buni tasdiqlaydi: 15 da 8 soat, 14 da allaqachon 9 soat. firstTrue endi qayta ishlatiladigan shablon: masalaga faqat chegaralar va predikat kerak.

Bu masalada n — qozonlar soni, S — eng katta qozon. Vaqt: O(n · log S). Qozonda milliard dona bo'lsa ham, log₂ 10⁹ ≈ 30 ta tekshiruv.

Endi ikki masalani yonma-yon qo'ying — retsept bitta:

1. Javob nima? Son: sig'im, tezlik, vaqt.
2. Tekshiruv yozing: "shu javob yetadimi?" — odatda bitta sikl, O(n).
3. Monotonlikni tekshiring: kichik misolda jadval tuzing — "yo'q"lar va "ha"lar aralashmasin.
4. Chegaralarni tanlang: lo — mumkin bo'lgan eng kichik javob, hi — albatta "ha".
5. firstTrue(lo, hi, isGood) — tayyor.

Tekshirib ko'ring: Agar maxHours qozonlar sonidan kichik bo'lsa (masalan, 5 qozon, 4 soat), nima bo'ladi?

6. Taqsimlash masalalari

6.1 Ish yukini bo'lish

Yana bir masala. Ketma-ket kelgan 8 ta buyurtmani 3 ta oshpazga bo'lish kerak: har oshpaz ketma-ket bo'lakni oladi. Eng ko'p ishlagan oshpazning yuki iloji boricha kichik bo'lsin.

Tanish tuyuldimi? Bu sumka masalasining aynan o'zi: "oshpaz" — "kun", "yuk" — "sumka sig'imi". "Eng katta yukni minimallashtirish" = "eng kichik yetarli sig'im". minCapacity(weights, 3) javob beradi — 16. LeetCode'da bu 410 "Split Array Largest Sum" deb ataladi va "qiyin" toifasida turadi. Shablonni bilsangiz — u 1011 "Capacity To Ship Packages Within D Days" bilan bir xil.

6.2 Naqshni qanday tanish mumkin

Masala shartida shu belgilarni qidiring:

6.3 Teskari shakl: eng kichigini maksimallashtirish

Teskari shakl ham bor: "eng kichigini maksimallashtiring". «Bahor» zalida stol qo'yish mumkin bo'lgan bo'sh joylar bor — kirish eshigidan 1, 2, 4, 8 va 9 metrda. Jasur aka 3 ta stol qo'ymoqchi. Mehmonlar bir-biriga xalaqit bermasin: eng yaqin ikki stol orasidagi masofa iloji boricha katta bo'lsin.

Uch savolni yana beramiz:

1. Tekshiruv: "kamida d metr oraliq bilan 3 ta stol sig'adimi?" Birinchi stolni eng chetga qo'yamiz. Keyin joylarni chapdan yurib, oldingi stoldan kamida d uzoqdagi birinchi joyga keyingisini qo'yamiz. Bu yana greedy tekshiruv — O(n).
2. Monotonlik: d o'sgan sari stollarni joylash qiyinlashadi. 3 metrda sig'sa, 2 metrda ham sig'adi. Javoblar: avval "ha", keyin faqat "yo'q". Endi bizga oxirgi "ha" kerak.
3. Chegaralar: d = 1 — eng kichik masofa. Eng chetdagi ikki joy orasidan (bu yerda 9 − 1 = 8) katta masofada ikki stol ham sig'maydi.

Oxirgi "ha" ni topish uchun yangi funksiya yozish shart emas. Oxirgi "ha" dan keyin darhol birinchi "yo'q" keladi. Demak, "sig'maydimi?" savoli uchun firstTrue ni chaqiramiz va natijadan bittani ayiramiz:

// [lo, hi] oralig'ida isGood rost bo'ladigan eng kichik son
function firstTrue(lo, hi, isGood) {
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (isGood(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

// kamida d metr oraliq bilan nechta stol sig'adi — yetadimi?
function canPlace(spots, tables, d) {
  let count = 1; // birinchi stol — eng chetdagi joyga
  let last = spots[0];
  for (const s of spots) {
    if (s - last >= d) {
      count++;
      last = s;
    }
  }
  return count >= tables;
}

function maxMinDistance(spots, tables) {
  const span = spots[spots.length - 1] - spots[0];
  // birinchi "sig'maydi" — span + 1 da albatta sig'maydi
  const tooFar = (d) => !canPlace(spots, tables, d);
  return firstTrue(1, span + 1, tooFar) - 1;
}

// zaldagi bo'sh joylar, kirish eshigidan metrda (saralangan)
const spots = [1, 2, 4, 8, 9];
console.log(maxMinDistance(spots, 3)); // 3
console.log(maxMinDistance(spots, 2)); // 8
console.log(canPlace(spots, 3, 4)); // false

Qo'lda tekshiramiz. d = 3: stollar 1, 4 va 8 metrga tushadi — 3 ta, sig'di. d = 4: 1 dan keyin kamida 5 metr kerak — 8; undan keyin kamida 12 — bunday joy yo'q. Atigi 2 ta stol. Demak, javob — 3 metr. Bu LeetCode'dagi 1552 "Magnetic Force Between Two Balls" masalasining «Bahor» varianti.

Tekshirib ko'ring: Nega firstTrue ga yuqori chegara sifatida span emas, span + 1 berdik?

7. Chegaraviy holatlar

8. Ko'p uchraydigan xatolar

8.1 Math.max(...array) katta massivda

Sodda yechimda chegara Math.max(...weights) bilan olindi. Kichik massivda ishlaydi. O'lchov paytida esa 200 000 buyurtmada dastur yiqildi:

const weights = new Array(200000).fill(7); // 200 000 ta buyurtma
console.log(Math.max(...weights));

Konsolda:

RangeError: Maximum call stack size exceeded

Tarjimasi: "Chaqiruvlar stekining eng katta hajmi oshib ketdi". Lekin rekursiya yo'q-ku? Spread (...) massivning har elementini funksiyaning alohida argumenti qilib uzatadi. 200 000 argument stekka sig'maydi. Bizning kompyuterda chegara 120 000 va 150 000 orasida chiqdi. Tuzatish: katta massivda — oddiy sikl yoki reduce: weights.reduce((m, w) => Math.max(m, w), 0).

8.2 Noto'g'ri chegaralar

Pastki chegarani 0 yoki 1 qilib qo'ysak, daysNeeded eng og'ir buyurtmadan kichik sig'imda ham "son" qaytaradi. Masalan, 9 kg li buyurtma 5 kg li sumkaga sig'maydi, lekin kod uni baribir "bugungi kunga" qo'shadi. Natija — yolg'on kichik javob. Tuzatish: lo — haqiqatan mumkin bo'lgan eng kichik javob (eng og'ir element), hi — albatta yetadigan javob.

8.3 Monoton bo'lmagan predikat

"Aynan 3 kun" kabi savol bilan binar qidiruv tasodifiy natija beradi — xato xabarisiz. Tuzatish: predikatni "ko'pi bilan" (≤) yoki "kamida" (≥) shaklida yozing va uning monotonligini kichik misolda jadval bilan tekshiring.

8.4 Yaxlitlash

hoursNeeded da b / speed ni yaxlitlamaslik: 30 / 12 = 2,5 soat — oshpaz esa chala soatni ham to'liq soat sarflaydi. Tuzatish: Math.ceil.

9. Mashqlar

1-mashq (oson): Chegaralarni ayting

Buyurtmalar [4, 10, 6, 2], 2 kunda yetkazish kerak. Javob ustida binar qidiruv uchun hi qancha bo'ladi?

2-mashq (o'rta): Sodda va tez yechimni solishtiring

minCapacitySlow va minCapacity ni urug'li tasodifiy 2 000 ta buyurtmada (og'irlik 1–20, 10 kun) ishga tushiring. Natijalar bir xilmi? Har biri daysNeeded ni necha marta chaqirdi? Ishora: daysNeeded ichida tashqi hisoblagichni oshiring.

let calls = 0;
function daysNeeded(weights, capacity) {
  calls++;
  let days = 1;
  let load = 0;
  for (const w of weights) {
    if (load + w > capacity) {
      days++;
      load = 0;
    }
    load += w;
  }
  return days;
}

function minCapacity(weights, maxDays) {
  let lo = 0;
  let hi = 0;
  for (const w of weights) {
    lo = Math.max(lo, w);
    hi += w;
  }
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (daysNeeded(weights, mid) <= maxDays) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

function minCapacitySlow(weights, maxDays) {
  let capacity = 0;
  for (const w of weights) capacity = Math.max(capacity, w);
  while (daysNeeded(weights, capacity) > maxDays) capacity++;
  return capacity;
}

let seed = 35;
const random = () => (seed = (seed * 16807) % 2147483647);
const weight = () => 1 + (random() % 20);
const weights = Array.from({ length: 2000 }, weight);

calls = 0;
const fast = minCapacity(weights, 10);
console.log(`tez: ${fast}, chaqiruvlar ${calls}`);
calls = 0;
const slow = minCapacitySlow(weights, 10);
console.log(`sodda: ${slow}, chaqiruvlar ${calls}`);

tez: 2086, chaqiruvlar 14
sodda: 2086, chaqiruvlar 2067

3-mashq (qiyin): Oshpaz tezligi va testlar

kurs/mashqlar/14/34-javob/javob.test.mjs faylida firstTrue, hoursNeeded, minSpeed va sodda minSpeedSlow ni (1 dan boshlab bittalab) yozing. Testlar (node:test):

1. [30, 11, 23, 4, 20]: 5 soatda — 30, 6 soatda — 23.
2. Bitta qozon: 1 soatda — 7, 100 soatda — 1.
3. Topilgan k yetadi, k - 1 esa yetmaydi.
4. Urug'li tasodifiy 50 ta masala — natija sodda yechim bilan bir xil.

// kurs/mashqlar/14/34-javob/javob.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

// [lo, hi] oralig'ida isGood rost bo'ladigan eng kichik son
function firstTrue(lo, hi, isGood) {
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (isGood(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

// k dona/soat tezlikda nechta soat ketadi
function hoursNeeded(batches, speed) {
  let hours = 0;
  for (const b of batches) hours += Math.ceil(b / speed);
  return hours;
}

function minSpeed(batches, maxHours) {
  let biggest = 1;
  for (const b of batches) biggest = Math.max(biggest, b);
  const enough = (k) => hoursNeeded(batches, k) <= maxHours;
  return firstTrue(1, biggest, enough);
}

// sodda yechim: 1 dan boshlab bittalab
function minSpeedSlow(batches, maxHours) {
  let k = 1;
  while (hoursNeeded(batches, k) > maxHours) k++;
  return k;
}

test("misol: 5 qozon, 5 va 6 soat", () => {
  const batches = [30, 11, 23, 4, 20];
  assert.equal(minSpeed(batches, 5), 30); // har soat — bitta qozon
  assert.equal(minSpeed(batches, 6), 23);
});

test("chegaraviy: bitta qozon, ko'p vaqt", () => {
  assert.equal(minSpeed([7], 1), 7);
  assert.equal(minSpeed([7], 100), 1); // soatiga 1 dona ham yetadi
});

test("javob — haqiqatan eng kichik", () => {
  const batches = [30, 11, 23, 4, 20];
  const k = minSpeed(batches, 8);
  assert.ok(hoursNeeded(batches, k) <= 8); // k yetadi
  assert.ok(hoursNeeded(batches, k - 1) > 8); // k − 1 yetmaydi
});

test("sodda yechim bilan bir xil (urug'li tasodifiy)", () => {
  let seed = 35;
  const random = () => (seed = (seed * 16807) % 2147483647);
  for (let round = 0; round < 50; round++) {
    const n = 1 + (random() % 8);
    const size = () => 1 + (random() % 60);
    const batches = Array.from({ length: n }, size);
    const maxHours = n + (random() % 20); // kamida n soat
    const expected = minSpeedSlow(batches, maxHours);
    assert.equal(minSpeed(batches, maxHours), expected);
  }
});

✔ misol: 5 qozon, 5 va 6 soat (1.0343ms)
✔ chegaraviy: bitta qozon, ko'p vaqt (0.3713ms)
✔ javob — haqiqatan eng kichik (0.4661ms)
✔ sodda yechim bilan bir xil (urug'li tasodifiy) (1.9188ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 113.1505

4-mashq: Amaliy tajriba — jadvalga uch qator

kurs/mashqlar/14/MURAKKABLIK.md ga qo'shing: minimal sig'im (bittalab va binar), minimal tezlik. S — javoblar oralig'i ekanini izohda yozing.

| Masala | Yechim | Vaqt | Xotira | Shart |
|---|---|---|---|---|
| Minimal sumka sig'imi | bittalab sinash | O(n · S) | O(1) | — |
| Minimal sumka sig'imi | javob ustida binar | O(n · log S) | O(1) | monoton predikat |
| Oshpazning minimal tezligi | javob ustida binar | O(n · log S) | O(1) | monoton predikat |

git add 14/MURAKKABLIK.md 14/34-javob
git commit -m "14/34: javob ustida binary search"

10. Real ishda

• Resurslarni rejalash. "Shu yukni ko'tarish uchun eng kamida nechta server kerak?", "Video uzatish uchun eng past qaysi bitreyt yetadi?" — predikat (modellash yoki sinov) bilan javob ustida qidiruv.
• Interfeys. Matn tugmaga sig'ishi uchun eng katta shrift o'lchami: "shu o'lchamda sig'adimi?" — monoton. Ba'zi "auto-fit" kutubxonalari aynan shunday ishlaydi.
• Git. git bisect ham aslida javob ustida qidiruv: "shu commitda xato bormi?" — tarix bo'yicha monoton (bir marta paydo bo'lgan xato keyin ham bor).
• Intervyu. LeetCode 875, 1011, 410, 1552 — bitta shablon. Intervyuchi ko'pincha avval sodda yechimni, keyin "tezroq bo'ladimi?" deb so'raydi. Monotonlikni ko'rsatish — yarim javob.

Xulosa

• Javob son bo'lsa va "shu javob yetadimi?" savoli monoton bo'lsa — javobning o'zini binar qidiring.
• Uch qism: predikat (odatda O(n) greedy tekshiruv), pastki chegara lo, albatta "ha" bo'ladigan yuqori chegara hi.
• Vaqt — O(n · log S); bittalab sinash — O(n · S), o'lchovda n ×2 → vaqt ×4.
• "Eng kattasini minimallashtirish" va "eng kichigini maksimallashtirish" — bitta shablonning ikki yo'nalishi.
• Katta massivda Math.max(...arr) yiqiladi — sikl yoki reduce ishlating.

Keyingi dars: Quickselect va k-chi element — butun massivni saralamasdan medianani yoki k-chi eng kichik elementni o'rtacha O(n) da topish.

Manbalar

• LeetCode 875 "Koko Eating Bananas", 1011 "Capacity To Ship Packages Within D Days", 410 "Split Array Largest Sum" — leetcode.com
• Steven Halim, Felix Halim, "Competitive Programming 4", 2020 — "Binary Search the Answer" bo'limi.
• MDN: "Spread syntax (...)" — argumentlar soni chegarasi haqida eslatma — developer.mozilla.org