Binary search variantlari: lower bound, upper bound, aylantirilgan massiv va matritsa

Qisqacha: Ko'pincha "qiymat bormi?" emas, "qayerdan boshlanadi?" degan savol bo'ladi. Lower bound — target dan katta yoki teng birinchi element indeksi, upper bound — target dan qat'iy katta birinchi element indeksi. Ikkalasi yarim ochiq oyna [left, right) bilan yoziladi: while (left < right), right = mid. Ular bilan birinchi va oxirgi uchrashni topish, takrorlarni O(log n) da sanash, yangi elementni tartibni buzmay qo'yish mumkin. Aylantirilgan massivda va saralangan matritsada ham g'oya bir xil: har qadamda yarmini (yoki bir qatorni) tashlash.

Bu darsda

• lowerBound va upperBound ni yarim ochiq oyna bilan yozasiz va ularning farqini tushuntira olasiz.
• Birinchi va oxirgi uchrashni topasiz, takrorlarni filtrsiz sanaysiz.
• Aylantirilgan (rotated) saralangan massivda O(log n) da qidirasiz.
• Saralangan matritsada ikki usulda qidirasiz: "bitta uzun ro'yxat" va "zinapoya".

Oldin bilishingiz kerak: Binary search asoslari, Matritsa bilan ishlash, Ikki ko'rsatkich.

1. Nega bu kerak?

O'tgan darsda binar qidiruvni yozdik. Lekin oxirida bitta muammo qoldi: binarySearch([5, 5, 5], 5) — 1. Takrorlar bo'lsa, u istalgan mos indeksni qaytaradi.

«Bahor»da bron soatlari tartiblangan ro'yxatda turadi: [18, 18, 19, 19, 19, 19, 20, 21, 21, 22]. Jasur akaning savollari esa boshqacha:

1. "Soat 19 da nechta bron bor?" — sanash kerak.
2. "Birinchi 19-lik bron qaysi?" — birinchi uchrash.
3. "Yangi bron 20:00 ga keldi. Ro'yxatning qayeriga qo'yay, tartib buzilmasin?" — qo'yish joyi.

Uchalasiga ham bitta javob bor: chegarani topish. "19 qayerdan boshlanadi va qayerda tugaydi?" Chegarani topadigan binar qidiruv — bugungi darsning asosiy qahramoni.

2. Lower bound — birinchi "katta yoki teng"

2.1 Savolni o'zgartiramiz

"19 qayerda?" emas, "birinchi ≥ 19 element qayerda?" deb so'raymiz. Bu savolning javobi doim bor — hatto 19 ro'yxatda bo'lmasa ham. Ro'yxatga qarang:

indeks:  0   1   2   3   4   5   6   7   8   9
qiymat: 18  18  19  19  19  19  20  21  21  22
>= 19?   –   –   ✓   ✓   ✓   ✓   ✓   ✓   ✓   ✓

"≥ 19?" savoliga javoblar ketma-ketligi monoton: avval faqat "yo'q", keyin faqat "ha". Bizga birinchi "ha" kerak — 2-indeks. Hamma element 19 dan kichik bo'lsa-chi? Unda birinchi "ha" yo'q va javob — length (oxiridan keyingi joy). Shuning uchun javob 0 dan length gacha bo'lishi mumkin.

2.2 Yarim ochiq oyna

Javob length ga teng bo'lishi mumkin bo'lgani uchun oynani boshqacha olamiz: [left, right) — left kiradi, right kirmaydi. Bunday oyna yarim ochiq oraliq deyiladi. Boshida right = length.

Hayotdan rasm: kassa oldidagi navbat. left — navbatdagi birinchi odam, right — navbat oxiridagi bo'sh joy, "keyingi kelgan shu yerga turadi". Bo'sh joyda hali hech kim yo'q, lekin u ham manzil — yangi bron aynan o'sha yerga qo'yilishi mumkin. Shuning uchun right oynaga "kirmaydi", lekin javob bo'la oladi. Invariant:

Javob doim left dan right gacha (ikkala chet ham mumkin).

Va qoidalar:

• sorted[mid] < target — mid va undan chapdagilar javob emas: left = mid + 1.
• sorted[mid] >= target — mid javob bo'lishi mumkin, uni tashlab bo'lmaydi: right = mid.
• left === right bo'lganda javob topildi: while (left < right).

O'tgan darsdagi yopiq oynadan farqqa qarang: u yerda <= va mid - 1 edi. Bu yerda < va right = mid. Ikkala uslub ham to'g'ri — faqat aralashtirmaslik kerak.

Ro'yxatda 10 ta soat bor, 3 qadam yetdi. Va javob takrorlar orasidan aynan birinchisi. E'tibor bering: 1-qadamda mid 19 ga tushdi, lekin qidiruv to'xtamadi. O'tgan darsdagi binarySearch esa birinchi duch kelgan 19 da to'xtaydi: binarySearch(hours, 19) — 4, birinchi 19 emas. Lower bound esa "chaprog'ida yana 19 bormi?" deb davom etadi.

2.3 Kod

function lowerBound(sorted, target) {
  let left = 0;
  let right = sorted.length; // oyna [left, right) — right kirmaydi
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (sorted[mid] < target) left = mid + 1;
    else right = mid; // mid ham javob bo'lishi mumkin
  }
  return left; // birinchi >= target joy
}

const hours = [18, 18, 19, 19, 19, 19, 20, 21, 21, 22];
console.log(lowerBound(hours, 19)); // 2
console.log(lowerBound(hours, 17)); // 0 — hammasidan kichik
console.log(lowerBound(hours, 23)); // 10 — hammasidan katta
console.log(lowerBound(hours, 19.5)); // 6 — 19 va 20 orasi

Nega bu yerda cheksiz sikl bo'lmaydi? right = mid mid ni oynada qoldiradi-ku. Javob: mid = Math.floor((left + right) / 2) doim right dan qat'iy kichik (chunki left < right). Demak, right = mid oynani albatta qisqartiradi. left = mid + 1 ham. Har aylanishda oyna kamida bittaga kichrayadi.

Tekshirib ko'ring: lowerBound([], 5) nima qaytaradi va nega bu to'g'ri?

3. Upper bound va undan foydalanish

3.1 Birinchi "qat'iy katta"

Upper bound — target dan qat'iy katta birinchi element. Kodda bitta belgi farq qiladi: < o'rniga <=.

«Bahor» tilida: lower bound — "19-lik bronlar qayerdan boshlanadi", upper bound — "19-liklardan keyingi birinchi bron qayerda". sorted[mid] 19 ga teng bo'lsa, lower bound uni "javob bo'lishi mumkin" deb ushlab qoladi. Upper bound esa "bu hali 19, javob o'ngroqda" deb o'tib ketadi. Kuzating:

Ikki ko'rsatkich 6 da uchrashdi — 19-liklar bloki tugagan joyda. Endi ikkala funksiyani birga ishlatamiz:

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

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

const hours = [18, 18, 19, 19, 19, 19, 20, 21, 21, 22];
const first = lowerBound(hours, 19);
const afterLast = upperBound(hours, 19);
console.log(first, afterLast);
console.log(`19 da ${afterLast - first} ta bron`);
console.log(`oxirgi 19: ${afterLast - 1}-indeks`);

Konsolda:

2 6
19 da 4 ta bron
oxirgi 19: 5-indeks

[lowerBound, upperBound) — target ga teng hamma elementlar oralig'i. Undan uch narsa chiqadi:

Agar target umuman yo'q bo'lsa, ikkala chegara bir xil chiqadi: lowerBound(hours, 17) va upperBound(hours, 17) — ikkalasi 0. Soni — 0.

3.2 Tartibni buzmay qo'shish

Yangi bron 20:00 ga keldi. Uni upperBound joyiga qo'ysak, ro'yxat tartibda qoladi va mavjud 20-lardan keyin tushadi — kelish tartibi saqlanadi:

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

const hours = [18, 18, 19, 19, 20, 21, 22];
const index = upperBound(hours, 20);
hours.splice(index, 0, 20); // index ga 20 ni qo'yamiz
console.log(index, hours.join(" ")); // 5 18 18 19 19 20 20 21 22

Joyni topish — O(log n). Lekin splice o'rtaga qo'yish uchun keyingi hamma elementlarni suradi — O(n) (Massiv joyida amallar). Ko'p qo'shish bo'lsa, boshqa tuzilma kerak: Binary Search Tree yoki Heap.

Tekshirib ko'ring: Bron ro'yxatida 21 dan kichik bronlar nechta? Bitta funksiya chaqiruvi bilan javob bering.

4. O'lchov: filtr bilan sanash va chegaralar bilan sanash

"Soat t da nechta bron?" — sodda yechim hours.filter((h) => h === t).length — O(n). Chegaralar bilan — O(log n). Ikkalasini Performansni o'lchash darsidagi usul bilan o'lchadik: har n alohida jarayonda, avval isitish, urug'li ma'lumot, 7 o'lchovning medianasi:

Ustunlarning sarlavhasiga qarang: chap ustunda 100 ta sanash, o'ngda — 100 000 ta. Ya'ni n = 800 000 da bitta filter sanashi ≈ 4,9 ms, bitta chegara sanashi ≈ 0,64 mikrosoniya — taxminan 7 600 baravar tez. Ro'yxat ikki baravar oshganda filter ikki baravar sekinlashdi, chegaralar esa deyarli o'zgarmadi.

5. Umumiy shakl: monoton savolning birinchi "ha"si

5.1 Ikki funksiya — bitta g'oya

lowerBound va upperBound ning farqi faqat savolda edi: "sorted[i] >= target?" va "sorted[i] > target?". Ikkala savol ham monoton: indeks o'sgan sari javob bir marta "yo'q" dan "ha" ga o'tadi va qaytib "yo'q" bo'lmaydi. Bizga doim birinchi "ha" kerak edi.

Demak, savolni tashqaridan beradigan bitta umumiy funksiya yozish mumkin. Savol — predikat (predicate): true yoki false qaytaradigan funksiya (Callback kabi uzatiladi):

// [lo, hi) oralig'ida isGood rost bo'ladigan birinchi son
function firstTrue(lo, hi, isGood) {
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (isGood(mid)) hi = mid; // javob — mid yoki chaprog'ida
    else lo = mid + 1;
  }
  return lo; // hech biri yaxshi bo'lmasa — hi
}

const prices = [5000, 12000, 18000, 25000, 28000, 30000, 35000];
const n = prices.length;

// lower bound — firstTrue ning bir holati
console.log(firstTrue(0, n, (i) => prices[i] >= 25000)); // 3

// byudjetga eng yaqin narx: 26 000 so'm
const budget = 26000;
const i = firstTrue(0, n, (k) => prices[k] >= budget);
const near = [prices[i - 1], prices[i]];
const candidates = near.filter((p) => p !== undefined);
const closest = candidates.reduce((a, b) =>
  Math.abs(a - budget) <= Math.abs(b - budget) ? a : b,
);
console.log(closest); // 25000

firstTrue sonlar oralig'ida ishlaydi, massiv bilan emas. Massiv faqat predikat ichida ishlatiladi. Bu juda muhim farq: keyingi darsda massiv umuman bo'lmaydi — biz javobning o'zini oraliqda qidiramiz.

5.2 Eng yaqin qiymat

Ikkinchi misolga qarang. Dilshod akaning byudjeti 26 000 so'm: "Narxi shunga eng yaqin taom qaysi?" Lower bound birinchi ≥ 26 000 narxni beradi — 28 000. Lekin eng yaqini undan oldingisi ham bo'lishi mumkin — 25 000. Shuning uchun ikki qo'shnini solishtiramiz: i - 1 va i.

Chegaraviy holatlarga e'tibor bering. Byudjet hammasidan kichik bo'lsa, i = 0 va prices[-1] — undefined. Hammasidan katta bo'lsa, i = n va prices[n] — undefined. filter ularni tashlab yuboradi — qolganlardan eng yaqini olinadi. reduce ikkita nomzoddan masofasi kichigini tanlaydi (reduce).

Tekshirib ko'ring: Narxlar ro'yxatida "26 000 dan arzon eng qimmat taom" qaysi? Qaysi indeksni olasiz?

6. Aylantirilgan massivda qidirish

6.1 Masala

«Bahor»ning tungi kassasi buyurtma soatlarini yozib boradi. Smena 21:00 da boshlanadi, yarim tundan keyin soat 0 dan qayta sanaladi: [21, 22, 23, 0, 1, 2, 4, 6, 8, 10, 15]. Bu — aylantirilgan saralangan massiv (rotated sorted array): saralangan ro'yxat bir joyidan kesilib, ikki bo'lagi o'rin almashgan.

Oddiy binar qidiruv bu yerda adashadi: 4 ni qidirganda o'rtadagi 2 ni ko'rib, "4 katta — o'ngga" deydi. Bu safar tasodifan to'g'ri. Lekin 22 ni qidirsa, 2 < 22 bo'lgani uchun o'ngga ketadi — 22 esa chapda. O'ng tomonda 4, 6, 8, 10, 15 — 22 u yerda yo'q. Oddiy qidiruv -1 qaytaradi va xato haqida hech narsa demaydi.

Nega shunday bo'ldi? Oddiy binar qidiruv "o'rtadan chapdagilar hammasi kichik" deb ishonadi. Bu yerda esa chapda 21, 22, 23 — o'rtadagi 2 dan katta sonlar turibdi. Saralanganlik buzilgan, demak qoida ham buziladi.

6.2 G'oya: bir yarmi doim tartibli

O'rtadan kessak, "uzilish" (23 dan 0 ga sakrash) ikki yarmdan faqat bittasiga tushadi. Ikkinchisi oddiy saralangan bo'lak. Qaysi biri tartibli ekanini bitta solishtirish aytadi: arr[left] <= arr[mid] bo'lsa — chap yarmi tartibli. Tartibli yarmda target bor-yo'qligini chetlariga qarab bilamiz. Bor bo'lsa — o'sha tomonga, yo'q bo'lsa — ikkinchisiga:

6.3 Kod

function searchRotated(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[left] <= arr[mid]) { // chap yarmi tartibli
      if (arr[left] <= target && target < arr[mid]) right = mid - 1;
      else left = mid + 1;
    } else { // o'ng yarmi tartibli
      if (arr[mid] < target && target <= arr[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return -1;
}

const log = [21, 22, 23, 0, 1, 2, 4, 6, 8, 10, 15];
console.log(searchRotated(log, 4)); // 6
console.log(searchRotated(log, 22)); // 1
console.log(searchRotated(log, 5)); // -1
console.log(searchRotated([8, 10, 15], 10)); // 1 — aylantirilmagan

Endi 22 ni — oddiy qidiruvni adashtirgan qiymatni — qo'lda kuzatamiz:

1. mid = 5, arr[5] = 2. arr[0] = 21 > 2 — chap yarmi tartibli emas, demak o'ng yarmi [2 … 15] tartibli. 22 undan katta — o'ng yarmda yo'q. Chapga boramiz: right = 4.
2. mid = 2, arr[2] = 23. 21 ≤ 23 — chap yarmi [21, 22, 23] tartibli. 22 uning ichida (21 ≤ 22 < 23): right = 1.
3. mid = 0, arr[0] = 21. Chap "yarm" — faqat 21 ning o'zi, 22 unda yo'q: left = 1.
4. mid = 1, arr[1] = 22. Topildi!

Har qadamda faqat tartibli yarmga qarab qaror qildik — u yerda chetlarni solishtirish ishonchli.

Bu yerda yopiq oyna [left, right] — chunki aniq qiymatni qidiryapmiz, chegarani emas. Shartdagi <= muhim: oyna ikki elementli bo'lganda left === mid va chap "yarm" bitta elementdan iborat — u tartibli hisoblanadi.

Vaqt — O(log n), xotira — O(1). Bu masala LeetCode'da 33 "Search in Rotated Sorted Array" nomi bilan mashhur.

Diqqat: Bu kod faqat takrorsiz massivda kafolat beradi. Masalan, [5, 5, 5, 1, 5] kabi massivda arr[left] === arr[mid] === arr[right] bo'lib qolsa, qaysi yarmi tartibli ekanini aniqlab bo'lmaydi — eng yomon holatda chiziqli qidiruvga aylanadi.

Xuddi shu "qaysi yarmi tartibli?" g'oyasi bilan aylantirish nuqtasini — eng kichik elementni (bu yerda 0, yarim tun) — ham O(log n) da topish mumkin. LeetCode'da bu 153 "Find Minimum in Rotated Sorted Array".

7. Matritsada qidirish

7.1 To'liq saralangan matritsa — bitta uzun ro'yxat

Narxlar jadvali shunday: har qator o'sib boradi va har qatorning birinchisi oldingi qatorning oxirgisidan katta. Unda jadval aslida bitta saralangan ro'yxat, faqat qatorlarga bo'lib yozilgan. k-element qaysi katakda? [Math.floor(k / cols), k % cols] (Matritsa bilan ishlash):

function searchSortedMatrix(matrix, target) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  let left = 0;
  let right = rows * cols - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const value = matrix[Math.floor(mid / cols)][mid % cols];
    if (value === target) return [Math.floor(mid / cols), mid % cols];
    if (value < target) left = mid + 1;
    else right = mid - 1;
  }
  return null;
}

const menuPrices = [
  [5, 8, 12],
  [15, 18, 20],
  [25, 28, 35],
];
console.log(searchSortedMatrix(menuPrices, 28)); // [ 2, 1 ]
console.log(searchSortedMatrix(menuPrices, 30)); // null

Formulani bitta misolda tekshiramiz. Jadvalda 3 ta ustun bor (cols = 3). "Bitta uzun ro'yxat"da 7-o'rin qayerda? Qator — Math.floor(7 / 3) = 2, ustun — 7 % 3 = 1. menuPrices[2][1] — 28. Ro'yxat shaklida yozsak: 5, 8, 12, 15, 18, 20, 25, 28, 35 — haqiqatan 7-indeks (0 dan sanaganda).

R qator va C ustunda — O(log(R · C)). Jadvalni massivga "yoyib" nusxa olish shart emas: indeksni hisoblash yetadi.

7.2 Faqat qator va ustunlar saralangan — zinapoya

Ikkinchi xil jadval: har qator chapdan o'ngga, har ustun yuqoridan pastga o'sadi, lekin qatorlar bir-birining davomi emas. Masalan, 2-qator 6 dan boshlanadi, 1-qator esa 20 gacha boradi. Endi "bitta ro'yxat" hiylasi ishlamaydi.

Yuqori o'ng burchakka qarang. U o'z qatorining eng kattasi va o'z ustunining eng kichigi. Shuning uchun undan boshlasak, har solishtirish butun bir qator yoki ustunni tashlaydi:

R + C dan ko'p bo'lmagan qadam — O(R + C). Bu binar qidiruv emas — ikki ko'rsatkich naqshiga yaqin. Lekin g'oyasi bir xil: monoton tartibdan foydalanib, javob bo'lishi mumkin bo'lmagan qismni tashlash. LeetCode'da bu 240 "Search a 2D Matrix II", birinchi variant esa 74 "Search a 2D Matrix".

Tekshirib ko'ring: Zinapoya qidiruvini yuqori chap burchakdan boshlasa bo'ladimi?

8. Chegaraviy holatlar

Aylantirilgan massivda: bitta element, aylantirilmagan (0 marta) va to'liq aylantirilgan (n marta — yana o'zi) holatlarini albatta sinang. Matritsada: bo'sh matritsa (matrix[0] — undefined!) va bitta qatorli matritsa.

9. Ko'p uchraydigan xatolar

9.1 Ikki uslubni aralashtirish

right = sorted.length (yarim ochiq) bilan while (left <= right) (yopiq) — sorted[mid] oxiridan tashqariga chiqadi va undefined bilan solishtiriladi. Yoki right = mid bilan <= — cheksiz sikl. Tuzatish: bitta uslubni tanlang va uni oxirigacha saqlang: yopiq [l, r] → <=, mid ± 1; yarim ochiq [l, r) → <, right = mid.

9.2 Lower bound natijasini tekshirmaslik

lowerBound — "qo'yish joyi", "topildi" emas. lowerBound(hours, 17) — 0, lekin hours[0] — 18. Tuzatish: index < length && sorted[index] === target ni tekshiring.

9.3 Upper bound'ni "oxirgi uchrash" deb o'ylash

upperBound(hours, 19) — 6, oxirgi 19 esa 5-indeksda. Tuzatish: oxirgi uchrash — upperBound - 1, va faqat soni noldan katta bo'lsa.

9.4 Bo'sh matritsa

matrix[0].length bo'sh matritsada TypeError: Cannot read properties of undefined (reading 'length') beradi. Tuzatish: boshida if (matrix.length === 0) return null;.

10. Mashqlar

1-mashq (oson): Chegaralarni toping

a = [3, 5, 5, 5, 8, 13] uchun lowerBound(a, 5) va upperBound(a, 5) ni qo'lda toping. 5 dan nechta bor? Sonni yozing:

2-mashq (o'rta): Narx oralig'idagi taomlar

Menyu narxlari saralangan: [5000, 12000, 18000, 25000, 28000, 30000, 35000, 42000]. countInRange(prices, low, high) funksiyasini yozing: narxi low dan high gacha (ikkalasi ham kiradi) bo'lgan taomlar soni. O(log n) bo'lsin.

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

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

function countInRange(prices, low, high) {
  return upperBound(prices, high) - lowerBound(prices, low);
}

const prices = [5000, 12000, 18000, 25000,
  28000, 30000, 35000, 42000];
console.log(countInRange(prices, 20000, 30000)); // 3
console.log(countInRange(prices, 30000, 30000)); // 1
console.log(countInRange(prices, 1000, 4000)); // 0

3-mashq (qiyin): searchRange va testlar

kurs/mashqlar/14/33-variantlar/variant.test.mjs faylida lowerBound, upperBound va searchRange(sorted, target) ni yozing. searchRange birinchi va oxirgi uchrash indeksini [first, last] ko'rinishida qaytarsin, target bo'lmasa — [-1, -1] (LeetCode 34). Testlar (node:test):

1. Bo'sh massiv.
2. Bron soatlari: 19, 22 (oxirgi element), 17 va 23 (chetdan tashqari).
3. Qo'yish joyi: hammasidan kichik, hammasidan katta, orasida.
4. Urug'li tasodifiy 300 ta son: -1 dan 41 gacha har qiymat uchun natija indexOf/lastIndexOf bilan, soni esa filter bilan bir xil.

// kurs/mashqlar/14/33-variantlar/variant.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

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

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

// [birinchi, oxirgi] indeks yoki [-1, -1]
function searchRange(sorted, target) {
  const first = lowerBound(sorted, target);
  if (first === sorted.length || sorted[first] !== target) {
    return [-1, -1];
  }
  return [first, upperBound(sorted, target) - 1];
}

test("chegaraviy: bo'sh massiv", () => {
  assert.equal(lowerBound([], 5), 0);
  assert.equal(upperBound([], 5), 0);
  assert.deepEqual(searchRange([], 5), [-1, -1]);
});

test("bron soatlari: birinchi va oxirgi 19", () => {
  const hours = [18, 18, 19, 19, 19, 19, 20, 21, 21, 22];
  assert.deepEqual(searchRange(hours, 19), [2, 5]);
  assert.deepEqual(searchRange(hours, 22), [9, 9]);
  assert.deepEqual(searchRange(hours, 17), [-1, -1]);
  assert.deepEqual(searchRange(hours, 23), [-1, -1]);
});

test("qo'shish joyi: chetlar", () => {
  const a = [10, 20, 30];
  assert.equal(lowerBound(a, 5), 0); // hammasidan kichik
  assert.equal(lowerBound(a, 35), 3); // hammasidan katta — length
  assert.equal(lowerBound(a, 25), 2); // orasida
});

test("sodda yechim bilan bir xil (urug'li tasodifiy)", () => {
  let seed = 34;
  const random = () => (seed = (seed * 16807) % 2147483647);
  const arr = Array.from({ length: 300 }, () => random() % 40);
  arr.sort((x, y) => x - y);
  for (let t = -1; t <= 41; t++) {
    const first = arr.indexOf(t);
    const last = arr.lastIndexOf(t);
    assert.deepEqual(searchRange(arr, t), [first, last]);
    const count = arr.filter((x) => x === t).length;
    assert.equal(upperBound(arr, t) - lowerBound(arr, t), count);
  }
});

✔ chegaraviy: bo'sh massiv (1.2525ms)
✔ bron soatlari: birinchi va oxirgi 19 (0.1581ms)
✔ qo'shish joyi: chetlar (0.1084ms)
✔ sodda yechim bilan bir xil (urug'li tasodifiy) (1.7096ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 81.6044

4-mashq: Amaliy tajriba — jadvalga to'rt qator

kurs/mashqlar/14/MURAKKABLIK.md ga qo'shing: takrorlarni sanash (filter va chegaralar), aylantirilgan massivda qidiruv, matritsada qidiruv (ikki usul).

| Masala | Yechim | Vaqt | Xotira | Shart |
|---|---|---|---|---|
| Takrorlarni sanash | filter(...).length | O(n) | O(n) | yo'q |
| Takrorlarni sanash | upperBound − lowerBound | O(log n) | O(1) | saralangan |
| Aylantirilgan massivda qidiruv | yarmi tartibli | O(log n) | O(1) | takrorsiz |
| Matritsada qidiruv | zinapoya | O(R + C) | O(1) | qator va ustun saralangan |

git add 14/MURAKKABLIK.md 14/33-variantlar
git commit -m "14/33: lower/upper bound, rotated va matritsa"

11. Real ishda

• Standart kutubxonalar. C++ std::lower_bound/upper_bound, Python bisect_left/bisect_right — aynan bugungi ikki funksiya. JavaScript'da tayyori yo'q, shuning uchun loyihalarda ko'pincha o'zingiz yozasiz yoki kichik yordamchi faylda saqlaysiz.
• Vaqt qatorlari. Grafikda "soat 14:00 dan 16:00 gacha nuqtalar" — vaqt bo'yicha saralangan massivda ikki chegara. Monitoring tizimlari va moliyaviy grafiklar shunday ishlaydi.
• Ma'lumotlar bazasi. WHERE price BETWEEN 20000 AND 30000 indeks bo'yicha aynan lower va upper bound bilan bajariladi — keyin oradagi qatorlar o'qiladi.
• Intervyu. LeetCode 34 (birinchi va oxirgi pozitsiya), 33 (rotated), 74 va 240 (matritsa) — eng ko'p beriladigan binar qidiruv masalalari. Ko'pchilik yiqiladigan joy — chegara uslubini aralashtirish.

Xulosa

• Lower bound — birinchi ≥ target, upper bound — birinchi > target; javob 0 dan length gacha.
• Yarim ochiq oyna [left, right): while (left < right), left = mid + 1, right = mid.
• [lower, upper) — teng elementlar oralig'i: soni, birinchisi, oxirgisi O(log n) da.
• Aylantirilgan massivda bir yarmi doim tartibli — shuni aniqlab, baribir yarmini tashlaymiz.
• To'liq saralangan matritsa — bitta ro'yxat (O(log(R·C))); faqat qator va ustun saralangan bo'lsa — zinapoya (O(R + C)).

Keyingi dars: Javob ustida binary search — massivda emas, javobning o'zida qidirish: "eng kichik yetarli sig'im qancha?" kabi savollar.

Manbalar

• C++ hujjatlari: std::lower_bound, std::upper_bound — cppreference.com
• Python hujjatlari: bisect moduli — docs.python.org/3/library/bisect.html
• LeetCode 33, 34, 74, 240 — leetcode.com