Binary search asoslari: left, right, mid va sikl invarianti

Qisqacha: Binary search (ikkiga bo'lib qidirish) saralangan massivda o'rtadagi elementga qaraydi va qidirilgan qiymat qaysi yarmida ekanini aniqlaydi — ikkinchi yarmi tashlanadi. Har qadamda oyna yarmiga qisqaradi, shuning uchun million elementda ham ≈ 20 qadam: O(log n). To'g'ri yozishning kaliti — invariant: "qiymat bor bo'lsa, u doim [left, right] ichida". while (left <= right), left = mid + 1, right = mid - 1 — shu qoidadan kelib chiqadi.

Bu darsda

• Chiziqli va binar qidiruvni solishtirib, binar qidiruv qachon ishlashini aytasiz.
• left, right, mid ni invariant asosida yozasiz va har qatorni asoslay olasiz.
• Off-by-one (bittaga adashish) xatolarini va cheksiz siklni tanib, tuzatasiz.
• Iterativ va rekursiv variantni yozib, ularni bir xil testlar bilan tekshirasiz.

Oldin bilishingiz kerak: Asosiy murakkablik sinflari, Oddiy saralashlar, Rekursiv fikrlash, while sikli.

1. Nega bu kerak?

«Bahor» kassasida bir yillik cheklar arxivi bor — 1 000 000 ta chek, raqami bo'yicha tartiblangan. Mehmon telefon qildi: "Kecha 1 027 463-chekda xato bor edi." Kassir qidiradi.

Sardorning birinchi yechimi — boshidan bittalab ko'rib chiqish. Asosiy murakkablik sinflari darsida bu o'yinni ko'rgan edik: saralangan ro'yxatda o'rtasidan ochish ancha yaxshi. U yerda faqat g'oyani ko'rdik. Bugun shu algoritmni to'g'ri yozishni o'rganamiz.

Bu muhim: binary search — dasturlashdagi eng qisqa, lekin eng ko'p xato qilinadigan algoritmlardan biri. Jon Bentley "Programming Pearls" kitobida yozishicha, u professional dasturchilarga binary search yozishni topshirgan — tekshiruvda ularning taxminan 90 foizi kodida xato chiqqan. Xatolar doim bir xil joyda: chegaralarda. Bugun chegaralarni taxmin bilan emas, qoida bilan yozamiz.

2. Chiziqli va binar qidiruv

2.1 Ikki usul

Chiziqli qidiruv (linear search) — har elementni navbat bilan tekshirish. Ro'yxat saralangan bo'lishi shart emas. Eng yomon holatda n qadam — O(n).

Binar qidiruv (binary search) — saralangan ro'yxatda o'rtadan boshlash. Asosiy murakkablik sinflari darsida uni "ikkiga bo'lib qidirish" deb atagan edik — bu bitta algoritm. Har qadamda qolgan qism yarmiga qisqaradi — O(log n). Qadamlarni sanaymiz, chek ro'yxatda yo'q bo'lsin (eng yomon holat):

function linearSteps(sorted, target) {
  let steps = 0;
  for (const x of sorted) {
    steps++;
    if (x === target) break;
  }
  return steps;
}

function binarySteps(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;
  let steps = 0;
  while (left <= right) {
    steps++;
    const mid = Math.floor((left + right) / 2);
    if (sorted[mid] === target) break;
    if (sorted[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return steps;
}

for (const n of [100, 10_000, 1_000_000]) {
  const checks = Array.from({ length: n }, (_, i) => 1000 + i);
  const target = 999; // yo'q chek — eng yomon holat
  const lin = linearSteps(checks, target);
  const bin = binarySteps(checks, target);
  console.log(`n=${n}: chiziqli ${lin}, binar ${bin}`);
}

Konsolda:

n=100: chiziqli 100, binar 6
n=10000: chiziqli 10000, binar 13
n=1000000: chiziqli 1000000, binar 19

Million chekda — 19 qadam. Chiziqli qidiruv esa million qadam qiladi.

2.2 Binar qidiruvning sharti

Binar qidiruv bitta narsaga tayanadi: o'rtadagi element bilan solishtirish butun bir yarmini tashlashga ruxsat beradi. Bu faqat ro'yxat saralangan bo'lsa to'g'ri. Saralanmagan ro'yxatda u xato javob beradi — va xato haqida hech narsa demaydi.

Oxirgi qatorga qarang. Bitta qidiruv uchun avval saralash — chiziqli qidiruvdan qimmat. Lekin arxiv bir marta saralanib, kuniga yuzlab marta qidirilsa — binar qidiruv aniq yutadi.

3. Uch ko'rsatkich va invariant

3.1 Invariant nima

Avval uchta nomni eslaymiz. left — oynaning chap cheti, right — o'ng cheti, mid — o'rtasi. Oyna — ro'yxatning hali tekshirilmagan, "shubhali" qismi: javob faqat shu yerda bo'lishi mumkin. Ko'p kitob va saytlarda left va right o'rniga qisqa lo va hi (low — past, high — yuqori) yoziladi. Ma'nosi bir xil, kelasi darslarda ikkalasini ham uchratasiz.

Binary search'ni to'g'ri yozishning siri — bitta gap. Uni yozishdan oldin aytib olamiz:

Agar target massivda bo'lsa, u doim [left, right] oralig'ida turadi.

Bunday gap sikl invarianti (loop invariant) deyiladi — siklning har aylanishidan oldin ham, keyin ham rost bo'lib qoladigan o'zgarmas shart. U kodning "va'dasi": sikl qancha aylanmasin, bu gap buzilmaydi. Sayohatdagi kompasga o'xshaydi: qayerda turmang, u doim shimolni ko'rsatadi.

Endi kodning har qatorini shu va'dadan chiqaramiz:

1. Boshida: left = 0, right = length - 1. Oyna — butun massiv. Va'da rost: target bor bo'lsa, u shu yerda.
2. Sikl sharti: oyna bo'sh bo'lmaguncha ishlaymiz. [left, right] da kamida bitta element bor, qachonki left <= right. Shuning uchun <=, < emas.
3. sorted[mid] < target: mid va undan chapdagilar hammasi target dan kichik. Ular ichida target bo'lishi mumkin emas. Yangi chap chet — mid + 1. mid ning o'zi ham tashlanadi — uni allaqachon tekshirdik.
4. sorted[mid] > target: xuddi shunday, right = mid - 1.
5. Sikldan chiqish: left > right — oyna bo'sh. Va'da bo'yicha target faqat oyna ichida bo'lishi mumkin edi. Demak, u yo'q: -1.

3.2 Topilmagan holatni kuzatamiz

Asosiy murakkablik sinflari darsida topilgan holatni ko'rgan edik. Bu safar ro'yxatda yo'q chekni qidiramiz — oyna qanday bo'shab qolishini ko'rish uchun:

Oxirgi qadamga yana qarang. left va right bir-birini "kesib o'tdi": right = 4, left = 5. left aynan 1030 turishi kerak bo'lgan joyni ko'rsatmoqda — 1027 va 1034 orasini. Bu tasodif emas. Uni Binary search variantlari darsida "birinchi katta yoki teng element"ni topish uchun ishlatamiz.

3.3 Kod

function binarySearch(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1; // left > right: oyna bo'sh
}

const checks = [1003, 1008, 1015, 1021, 1027, 1034, 1040];
console.log(binarySearch(checks, 1021)); // 3
console.log(binarySearch(checks, 1030)); // -1
console.log(binarySearch([], 1021)); // -1

• Math.floor((left + right) / 2) — o'rtadagi indeks, pastga yaxlitlangan. Juft uzunlikdagi oynada ikki "o'rta" bor — chapdagisi olinadi.
• Bo'sh massivda right = -1, sikl bir marta ham aylanmaydi.

Tekshirib ko'ring: binarySearch([5, 8], 8) qadamlarini yozing: har qadamda left, right, mid qanday?

4. Off-by-one: bittaga adashish

Off-by-one xatosi — chegarani bittaga noto'g'ri qo'yish: < o'rniga <=, mid o'rniga mid + 1. Binary search'da ikki klassik variant bor. Ikkalasini qo'riqchi hisoblagich bilan ishga tushiramiz — aks holda biri dasturni qotirib qo'yadi:

// ❌ ikki xil xato variant
function searchLess(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;
  while (left < right) { // <= bo'lishi kerak edi
    const mid = Math.floor((left + right) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

function searchStuck(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;
  let rounds = 0;
  while (left <= right) {
    if (++rounds > 100) return "cheksiz sikl!"; // qo'riqchi
    const mid = Math.floor((left + right) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) left = mid; // mid + 1 kerak edi
    else right = mid - 1;
  }
  return -1;
}

const checks = [1001, 1005, 1012, 1020];
console.log(searchLess(checks, 1020)); // -1 — topmadi!
console.log(searchLess([1005], 1005)); // -1 — bitta elementda ham
console.log(searchStuck(checks, 1015)); // cheksiz sikl!

Birinchi xato — left < right. Oyna bitta elementga qisqarganda (left === right) sikl to'xtaydi va o'sha element tekshirilmaydi. Invariant tilida: oyna bo'sh emas edi, biz esa uni bo'sh deb hisobladik.

Ikkinchi xato — left = mid. Oyna ikki elementli bo'lsin: left = 2, right = 3. mid = 2. sorted[2] < target — left = mid = 2. Hech narsa o'zgarmadi! Keyingi aylanishda yana mid = 2 — va shunday abadiy. Qoida: har aylanish oynani kamida bittaga qisqartirishi shart. mid allaqachon tekshirilgan — uni oynada qoldirmang.

Diqqat: Cheksiz sikl xato xabarini bermaydi. Brauzerda sahifa qotadi, Node'da jarayon to'xtamaydi. Binary search yozayotganda har tarmoq uchun o'zingizdan so'rang: "Bu yerda oyna albatta kichrayadimi?"

Yuqoridagi kodda rounds — qo'riqchi hisoblagich: sikl 100 martadan ko'p aylansa, uni majburan to'xtatadi. 4 ta elementli ro'yxatda to'g'ri binar qidiruv 3 qadamdan oshmaydi, 100 — aniq xato belgisi. Bunday hisoblagichni faqat tajriba va testda qo'yamiz, tayyor kodda emas.

Tekshirib ko'ring: searchLess([1005, 1012], 1012) nima qaytaradi? Qadamlarni yozib ko'ring.

5. mid ni hisoblash nozikliklari

Avval bitta atama. Toshish (overflow) — son o'z "idishiga" sig'may qolishi. Mashinaning kilometr hisoblagichini eslang: 999 999 dan keyin u 000 000 ni ko'rsatadi. Ba'zi tillarda butun son ham shunday: chegaradan oshsa, g'alati — ko'pincha manfiy — qiymatga aylanadi.

Java dasturchilari 2006-yilgacha ko'p yillar davomida (left + right) / 2 ishlatib keldi. Keyin Joshua Bloch (Google) mashhur xatoni topdi: juda katta massivda left + right 32 bitli butun son chegarasidan (2 147 483 647) oshib, manfiy bo'lib qoladi. JDK'dagi binary search 9 yil shu xato bilan yashagan.

JavaScript'da oddiy sonlar 2⁵³ gacha aniq — left + right toshmaydi. Lekin tuzoq boshqa joyda. Ba'zan Math.floor o'rniga bit siljitish yoziladi: (left + right) >> 1 — bir bit o'ngga siljitish ikkiga bo'lib, pastga yaxlitlash bilan bir xil (Bitwise operatorlar). Bit amallari esa sonni 32 bitga qisqartiradi:

const left = 2 ** 31 - 1;
const right = 2 ** 31 - 1;
console.log(Math.floor((left + right) / 2)); // 2147483647
console.log((left + right) >> 1); // -1
console.log((left + right) >>> 1); // 2147483647

>> ishorali siljitish — katta yig'indini manfiy songa aylantirdi. >>> — ishorasiz siljitish, 2³² gacha to'g'ri ishlaydi. JavaScript massivining eng katta uzunligi 2³² − 1, shuning uchun indekslar uchun >>> 1 xavfsiz. Kursda biz Math.floor ishlatamiz — u har doim to'g'ri va tushunarli.

left + Math.floor((right - left) / 2) — yana bir mashhur yozuv. U boshqa tillarda toshishdan himoya qiladi. JavaScript'da natija Math.floor((left + right) / 2) bilan bir xil.

6. Rekursiv variant

Binary search tabiatan rekursiv: "oynaning yarmida xuddi shu masalani yech". Oynani parametr sifatida uzatamiz:

function search(sorted, target, left, right) {
  if (left > right) return -1; // oyna bo'sh
  const mid = Math.floor((left + right) / 2);
  if (sorted[mid] === target) return mid;
  if (sorted[mid] < target) {
    return search(sorted, target, mid + 1, right);
  }
  return search(sorted, target, left, mid - 1);
}

const prices = [5000, 12000, 18000, 25000, 28000, 30000, 35000];
console.log(search(prices, 28000, 0, prices.length - 1)); // 4
console.log(search(prices, 29000, 0, prices.length - 1)); // -1

Iterativ variant bilan solishtiring: while (left <= right) → asos holat left > right; left = mid + 1 → search(…, mid + 1, right). Har aylanish — bitta chaqiruv.

Rekursiv variantning steki log₂ n — million elementda ≈ 20 qavat, stek to'lishidan qo'rqmasa bo'ladi. Lekin amalda iterativ variant yoziladi: qo'shimcha xotira yo'q va chaqiruv narxi yo'q.

Tekshirib ko'ring: Rekursiv search da return so'zlarini unutib, faqat search(sorted, target, mid + 1, right); yozsangiz nima bo'ladi?

7. Obyektlar va taqqoslovchi bilan qidirish

Haqiqiy ilovada kamdan-kam hollarda sonlar ro'yxatida qidiramiz. Ko'pincha ro'yxatda obyektlar bo'ladi: taomlar, mehmonlar, cheklar. Ular biror kalit bo'yicha saralangan — masalan, taom nomi bo'yicha. Qidiruv ham o'sha kalit bo'yicha bo'lishi kerak.

Yechim — sort dan tanish usul: taqqoslash funksiyasini tashqaridan berish (sort va taqqoslash funksiyasi). Funksiya ikki narsani solishtiradi va son qaytaradi. Manfiy — chapdagi oldin turadi, 0 — teng, musbat — keyin turadi. Binar qidiruv < va === o'rniga shu sonning ishorasiga qaraydi:

// taqqoslovchi: manfiy — a oldin, 0 — teng, musbat — b oldin
function binarySearchBy(sorted, target, compare) {
  let left = 0;
  let right = sorted.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const c = compare(sorted[mid], target);
    if (c === 0) return mid;
    if (c < 0) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

const menu = [
  { name: "ko'k choy", price: 5000 },
  { name: "lag'mon", price: 28000 },
  { name: "manti", price: 30000 },
  { name: "osh", price: 35000 },
];
const byName = (dish, name) => dish.name.localeCompare(name);

const i = binarySearchBy(menu, "manti", byName);
console.log(i, menu[i].price); // 2 30000
console.log(binarySearchBy(menu, "somsa", byName)); // -1

Ikki narsaga qarang:

• byName ikki har xil narsani solishtiradi: chapda obyekt (taom), o'ngda satr (qidirilayotgan nom). Shuning uchun kalitni har safar obyektdan olamiz: dish.name.
• Menyu localeCompare tartibida saralangan va qidiruv ham localeCompare bilan. Saralash va qidiruvning tartibi bir xil bo'lishi shart. Menyu < bilan, qidiruv localeCompare bilan bo'lsa (yoki aksincha), ba'zi nomlar "topilmay" qoladi — xato xabarisiz.

Bu umumiy funksiya bir marta yoziladi va har qanday saralangan ro'yxatda ishlaydi: narx bo'yicha ((d, p) => d.price - p), sana bo'yicha, id bo'yicha. Vaqt baribir O(log n) — faqat har qadamda taqqoslovchining narxi qo'shiladi.

Tekshirib ko'ring: Menyu narx bo'yicha saralangan. 30 000 so'mlik taomni topish uchun binarySearchBy ga qanday taqqoslovchi berasiz?

8. O'lchov: n ikki baravar oshsa

Performansni o'lchash darsidagi usul bilan o'lchadik: har n alohida jarayonda, avval isitish, 7 o'lchovning medianasi. Bitta qidiruv juda tez — taymer uni sezmaydi. Shuning uchun bitta o'lchovda 100 000 ta binar qidiruv (yoki 1 000 ta chiziqli qidiruv) bajardik, qidiriladigan qiymatlar — urug'li tasodifiy:

Chiziqli qidiruvda n ×2 — vaqt ×2, toza O(n). Binar qidiruvda n 8 baravar oshdi, vaqt esa atigi 1,5 baravar. Nazariya: log₂ n 20 dan 23 ga — 1,15 baravar. Qolgan farq — xotira: 8 million sonli massiv (64 MB) protsessorning tez keshiga sig'maydi, har qidiruvdagi "sakrashlar" sekinroq xotiraga tushadi (Massiv xotirada). Baribir: bitta binar qidiruv 8 mln elementda ≈ 0,6 mikrosoniya, chiziqli esa 800 000 elementda ≈ 1,1 millisoniya — ikki ming baravar farq.

9. Chegaraviy holatlar

Takrorlarga e'tibor bering: binarySearch([5, 5, 5], 5) — 1, o'rtadagisi. Agar sizga birinchi uchrash kerak bo'lsa, oddiy binary search yetmaydi. Buni keyingi darsda hal qilamiz.

Yana bir chegaraviy holat — satrlar. Binar qidiruv satrlarda ham ishlaydi, lekin ro'yxat xuddi shu tartibda saralangan bo'lishi kerak. < satrlarni Unicode kodlari bo'yicha solishtiradi; ro'yxat localeCompare bilan saralangan bo'lsa, qidiruvda ham localeCompare ishlating.

10. Ko'p uchraydigan xatolar

10.1 Saralanmagan ro'yxat

binarySearch([30, 5, 35, 28], 5) → -1, garchi 5 bor bo'lsa ham. Xato xabari yo'q. Tuzatish: ma'lumot saralanganiga ishonch hosil qiling yoki testda shuni tekshiring.

10.2 while (left < right) va right = mid - 1 aralashmasi

Bitta elementli oyna tekshirilmaydi. Tuzatish: yopiq oyna [left, right] bilan doim <=. Keyingi darsda yarim ochiq oyna [left, right) ni ko'ramiz — u yerda < to'g'ri, lekin right = mid bo'ladi. Ikki uslubni aralashtirmang.

10.3 left = mid (yoki right = mid) yopiq oynada

Ikki elementli oynada cheksiz sikl. Tuzatish: tekshirilgan mid ni tashlang: mid + 1 va mid - 1.

10.4 indexOf o'rniga binar qidiruv — saralangan nusxada

Sardor massivni toSorted qilib, binar qidiruv bilan topilgan indeksni asl massivda ishlatdi. Indekslar mos emas! Tuzatish: indeks qaysi massivga tegishli ekanini aniq biling; ko'pincha indeks emas, qiymatning o'zi yoki obyekt kerak.

11. Mashqlar

1-mashq (oson): Qadamlarni sanang

16 ta elementli saralangan ro'yxatda binar qidiruv eng ko'pi bilan nechta qadam qiladi? Sonni yozing:

2-mashq (o'rta): Bron vaqti bormi?

«Bahor» bron vaqtlari kun boshidan daqiqalarda saqlanadi va saralangan: [600, 630, 720, 750, 780, 1140, 1200]. Masalan, 600 — bu 10:00, 1140 — 19:00. hasBooking(times, hhmm) funksiyasini yozing: "19:00" kabi satrni daqiqaga aylantirib, binar qidiruv bilan tekshirsin. Ishora: "19:00".split(":") — ["19", "00"] (satr metodlari).

function binarySearch(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

function hasBooking(times, hhmm) {
  const [h, m] = hhmm.split(":").map(Number);
  return binarySearch(times, h * 60 + m) !== -1;
}

const times = [600, 630, 720, 750, 780, 1140, 1200];
console.log(hasBooking(times, "19:00")); // true
console.log(hasBooking(times, "19:30")); // false
console.log(hasBooking(times, "10:00")); // true

3-mashq (qiyin): Ikki variant — bitta test to'plami

kurs/mashqlar/14/32-binar/binar.test.mjs faylida iterativ binarySearch va rekursiv searchRec ni yozing. Rekursiv variantda left va right uchun default qiymatlar bo'lsin (default parametrlar). Ikkala variantni bitta sikl ichida bir xil testlardan o'tkazing:

1. Bo'sh va bitta elementli massiv.
2. Birinchi va oxirgi element; hammasidan kichik va katta qiymat.
3. 0 dan 50 gacha har uzunlikda har element topiladi, ikki element orasidagi qiymat esa topilmaydi.

Uchinchi test "ehtimoliy" xatolarni ushlaydi: off-by-one ko'pincha faqat ma'lum uzunlikda (masalan, juft) chiqadi.

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

function binarySearch(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

// left va right berilmasa — butun massiv
function searchRec(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) return -1;
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid;
  if (arr[mid] < target) {
    return searchRec(arr, target, mid + 1, right);
  }
  return searchRec(arr, target, left, mid - 1);
}

const variants = [
  ["iterativ", binarySearch],
  ["rekursiv", searchRec],
];

for (const [name, fn] of variants) {
  test(`${name}: bo'sh va bitta element`, () => {
    assert.equal(fn([], 5), -1);
    assert.equal(fn([5], 5), 0);
    assert.equal(fn([5], 7), -1);
  });

  test(`${name}: chetlar va chetdan tashqari`, () => {
    const a = [10, 20, 30, 40, 50];
    assert.equal(fn(a, 10), 0);
    assert.equal(fn(a, 50), 4);
    assert.equal(fn(a, 5), -1); // hammasidan kichik
    assert.equal(fn(a, 55), -1); // hammasidan katta
  });

  test(`${name}: har uzunlikda har element topiladi`, () => {
    for (let n = 0; n <= 50; n++) {
      const a = Array.from({ length: n }, (_, i) => i * 3);
      for (let i = 0; i < n; i++) assert.equal(fn(a, i * 3), i);
      assert.equal(fn(a, -1), -1);
      assert.equal(fn(a, 1), -1); // ikki element orasidagi qiymat
    }
  });
}

✔ iterativ: bo'sh va bitta element (0.7762ms)
✔ iterativ: chetlar va chetdan tashqari (0.1429ms)
✔ iterativ: har uzunlikda har element topiladi (1.3685ms)
✔ rekursiv: bo'sh va bitta element (0.1555ms)
✔ rekursiv: chetlar va chetdan tashqari (0.1026ms)
✔ rekursiv: har uzunlikda har element topiladi (0.585ms)
ℹ tests 6
ℹ suites 0
ℹ pass 6
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 82.9923

4-mashq: Amaliy tajriba — jadvalga ikki qator

kurs/mashqlar/14/MURAKKABLIK.md ga chiziqli va binar qidiruvni (iterativ va rekursiv) qo'shing. "Shart" ustuniga binar qidiruvning talabini yozing.

| Masala | Yechim | Vaqt | Xotira | Shart |
|---|---|---|---|---|
| Chekni topish | chiziqli qidiruv | O(n) | O(1) | yo'q |
| Chekni topish | binary search (iterativ) | O(log n) | O(1) | saralangan |
| Chekni topish | binary search (rekursiv) | O(log n) | O(log n) stek | saralangan |

git add 14/MURAKKABLIK.md 14/32-binar
git commit -m "14/32: binary search, invariant va testlar"

12. Real ishda

• Ma'lumotlar bazasi indeksi. Indeks — saralangan tuzilma (B-tree); qidiruv binar qidiruvning ko'p tarmoqli varianti. "Indeks qo'shing" degan maslahat aslida "chiziqli qidiruvni logarifmikka aylantiring" degani (Balanslangan daraxtlar va B-tree).
• Git. git bisect — commitlar tarixida binar qidiruv: qaysi commit xato kiritganini log₂ n ta tekshiruvda topadi. 1 000 commitda — 10 ta.
• Frontend. Virtual ro'yxatlarda (minglab qator) qaysi qator ekranda ekanini topish — qatorlar balandliklari prefiks yig'indisi ichida binar qidiruv.
• Intervyu. "Binary search'ni yozing" — eng ko'p uchraydigan savollardan. Intervyuchi kodni emas, chegaralarni tekshiradi: bo'sh massiv, bitta element, <= nega. Invariantni ovoz chiqarib aytsangiz, ko'p savollarga oldindan javob berasiz.

Xulosa

• Binar qidiruv faqat saralangan ma'lumotda ishlaydi va O(log n): million elementda ≈ 20 qadam.
• Invariant: "target bor bo'lsa, u [left, right] ichida". Undan <=, mid + 1, mid - 1 kelib chiqadi.
• Off-by-one: left < right bitta elementni o'tkazib yuboradi; left = mid cheksiz siklga olib keladi.
• (left + right) >> 1 katta indekslarda buziladi; Math.floor yoki >>> 1 ishlating.
• Rekursiv variant ham O(log n), lekin stek ishlatadi; amalda iterativ yoziladi.

Keyingi dars: Binary search variantlari — aniq qiymat emas, chegara: birinchi va oxirgi uchrash, lower/upper bound, aylantirilgan massiv va matritsada qidiruv.

Manbalar

• Jon Bentley, "Programming Pearls", 2-nashr, Addison-Wesley, 2000 — 4-bob (binar qidiruv va invariantlar).
• Joshua Bloch, "Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken", Google Research blogi, 2006.
• MDN: "Right shift (>>)" va "Unsigned right shift (>>>)" — developer.mozilla.org