3.10-bob: Qidiruv algoritmlari (linear, binary)

3-QISM — Algoritm va ma'lumotlar tuzilmasi · 10-mavzu

1. Kirish va motivatsiya

Saralashni 3.9-bob bildik; endi uning juftligi — qidiruv (search) ni o'rganamiz. "Ma'lumotda biror element bormi/qayerda?" — dasturlashda eng ko'p uchraydigan amal. 3.1 va 3.6-bobda binary searchni qisqacha ko'rdik; endi uning kuchini, variantlarini va tuzoqlarini chuqur ochamiz.

Asosiy g'oya — bitta savol: ma'lumot tartiblanganmi? Agar yo'q — linear search (O(n), birma-bir). Agar ha — binary search (O(log n), yarmiga bo'lish) — million elementni ~20 qadamda topadi! Bu farq — saralashga sarflangan vaqtni oqlaydigan asosiy sabab.

O'xshatish: lug'atda so'z qidirish. Birinchi sahifadan oxirigacha birma-bir varaqlash — linear (sekin). Lekin lug'at alifbo bo'yicha tartiblangani uchun, o'rtadan ochib, "oldinroqmi/keyinroqmi?" deb yarmini tashlab borasiz — binary (tez). Hech kim lug'atni birinchi sahifadan qidirmaydi — binary tabiiy.

Nega muhim?

• Eng ko'p uchraydigan amal: ma'lumot bormi/qayerda.
• Binary search — O(log n) ning eng aniq misoli; uning variantlari (chegara topish) ko'p masalada.
• DB indeks (6.3, 6.9), avtokomplit, oraliq so'rovlar — binary search g'oyasiga tayanadi.
• Intervyu klassikasi (off-by-one tuzog'i bilan mashhur).

2. Nazariya — chuqur tushuntirish

2.1. Linear search — O(n)

Linear (chiziqli) qidiruv — elementlarni birma-bir tekshirish, topilguncha yoki oxirigacha:

function linearSearch(arr, qidirilgan) {
  for (let i = 0; i < arr.length; i++)
    if (arr[i] === qidirilgan) return i;   // topildi — indeks
  return -1;                                // topilmadi
}
// O(n) — eng yomon: oxirgi yoki yo'q; O(1) — eng yaxshi: birinchi

Qachon linear: ma'lumot tartiblanmagan, kichik, yoki bir martalik qidiruv (saralash arzimaydi). includes/indexOf/find 2.8-bob — ichkarida linear search.

2.2. Binary search — O(log n)

Binary (ikkilik) qidiruv — tartiblangan massivda; har qadamda o'rtani tekshirib, yarmini tashlaydi:

  [1, 3, 5, 7, 9, 11, 13]  7 ni qidir
  orta = 7  topildi! (1 qadam)

  [1, 3, 5, 7, 9, 11, 13]  11 ni qidir
  orta = 7 < 11  CHAP yarimni tashla, o'ngda qidir
  [9, 11, 13] orta = 11  topildi (2 qadam)

function binarySearch(arr, qidirilgan) {
  let chap = 0, ong = arr.length - 1;
  while (chap <= ong) {                       //  <= (teng bo'lganda ham)
    const orta = chap + Math.floor((ong - chap) / 2);   // overflow-xavfsiz (2.3)
    if (arr[orta] === qidirilgan) return orta;
    if (arr[orta] < qidirilgan) chap = orta + 1;  // o'ngda
    else ong = orta - 1;                          // chapda
  }
  return -1;
}
// O(log n) — har qadam yarmini tashlaydi; massiv TARTIBLANGAN bo'lishi SHART

Ikki tuzoq: (1) while (chap <= ong) — < emas (oxirgi elementni o'tkazib yuboradi). (2) chap = orta + 1, ong = orta - 1 — orta emas (cheksiz tsikl!). Bu — off-by-one 0.6-bob ning klassik manbai.

2.3. Nega chap + (ong - chap) / 2 (oddiy (chap + ong) / 2 emas)?

Katta sonlarda chap + ong overflow (0.1: MAX_SAFE_INTEGER) bo'lishi mumkin (boshqa tillarda jiddiy). chap + (ong - chap) / 2 — bir xil natija, lekin xavfsiz. JS'da kam muhim, lekin yaxshi odat.

2.4. Rekursiv binary search (3.11)

function binaryRec(arr, qidirilgan, chap = 0, ong = arr.length - 1) {
  if (chap > ong) return -1;                 // base case (3.11)
  const orta = chap + Math.floor((ong - chap) / 2);
  if (arr[orta] === qidirilgan) return orta;
  return arr[orta] < qidirilgan
    ? binaryRec(arr, qidirilgan, orta + 1, ong)   // o'ng yarim
    : binaryRec(arr, qidirilgan, chap, orta - 1); // chap yarim
}
// O(log n) vaqt, O(log n) xotira (rekursiya stack — 0.1, 2.4)

2.5. Binary search variantlari — chegara topish

Binary search faqat "bormi?" emas — chegaralar topishda ham kuchli:

• Birinchi/oxirgi uchrash (takror elementlar orasida).
• Lower bound — qidirilgandan kichik bo'lmagan birinchi element (>=).
• Upper bound — qidirilgandan katta birinchi element (>).
• Insert position — saralangan massivga qaerga qo'yish kerak.

// Lower bound: x dan kichik bo'lmagan birinchi indeks
function lowerBound(arr, x) {
  let chap = 0, ong = arr.length;            //  ong = length (chegara uchun)
  while (chap < ong) {
    const orta = chap + Math.floor((ong - chap) / 2);
    if (arr[orta] < x) chap = orta + 1;
    else ong = orta;                          // orta'ni saqla (>= bo'lishi mumkin)
  }
  return chap;
}
// [1,2,2,2,3], x=2  indeks 1 (birinchi 2)

Upper bound — < o'rniga <= yozsangiz (if (arr[orta] <= x)), x dan katta birinchi indeksni topadi. upperBound - lowerBound = x ning takrorlar soni.

2.6. 2D (matritsa) qidiruvi

Binary search bir o'lchamli massiv bilan cheklanmagan. Agar matritsa to'liq saralangan bo'lsa (har bir qator chapdan o'ngga o'sadi va keyingi qatorning birinchi elementi oldingi qatorning oxirgisidan katta), uni bitta uzun saralangan massiv deb qarab, oddiy binary search ishlatasiz — faqat orta indeksni satr/ustunga aylantiring:

// m×n to'liq saralangan matritsada qidiruv — O(log(m·n))
function search2D(matrix, x) {
  const m = matrix.length, n = matrix[0].length;
  let chap = 0, ong = m * n - 1;
  while (chap <= ong) {
    const orta = chap + Math.floor((ong - chap) / 2);
    const qiymat = matrix[Math.floor(orta / n)][orta % n];   // 1D  2D
    if (qiymat === x) return true;
    if (qiymat < x) chap = orta + 1;
    else ong = orta - 1;
  }
  return false;
}

Agar matritsa faqat qatorma-qator va ustunma-ustun saralangan bo'lsa (lekin to'liq emas), boshqa naqsh ishlaydi: yuqori-o'ng burchakdan boshlab, har qadamda satr yoki ustunni tashlab borasiz — O(m + n) ("zinapoya" qidiruvi). Qaysi tartib berilganini har doim tekshiring (off-by-one — 0.6 emas, balki noto'g'ri taxmin asosiy xato).

2.7. "Binary search on answer" naqshi

Binary search faqat massivda emas — monoton funksiya/javob oralig'i ustida ham ishlaydi. "Eng kichik X shundayki, shart bajariladi" tipidagi masalalar (ilg'or, 3.13):

  Masala: kemada N tovarni K kunda yetkazish uchun min sig'im?
  Javob oralig'i: [max tovar ... jami] — binary search bilan min sig'imni top
  (sig'im katta  kun kam; monoton  binary search ishlaydi)

2.8. Murakkablik va qachon qaysi

Qaror: bir martalik qidiruv, tartiblanmagan linear. Ko'p marta qidiruv bir marta sarala (O(n log n)), keyin har qidiruv O(log n). Yoki Hash Table (O(1) — 3.5) agar tartib kerak bo'lmasa.

2.9. Boshqa qidiruv tushunchalari

• Hash Table qidiruvi 3.5-bob — O(1), lekin tartibsiz.
• BST qidiruvi 3.6-bob — O(log n), tartiblangan, dinamik.
• DB indeks 6.9-bob — B-tree, binary search g'oyasi diskda.
• Tekst qidiruv — substring (KMP, 2.13: RegEx) — boshqa sinf.

3. Sintaksis — tez ma'lumotnoma

LINEAR:   birma-bir, O(n), tartiblanmagan; includes/indexOf/find 2.8-bob
BINARY:   tartiblangan, O(log n), yarmiga bo'lish
  while (chap <= ong); orta = chap + (ong-chap)/2;
  chap = orta+1 / ong = orta-1   (orta EMAS!)
VARIANTLAR: lower/upper bound, birinchi/oxirgi, insert position
QAROR:    1 marta  linear; ko'p marta  sort + binary; tartibsiz  Hash (3.5)

4. Batafsil kod namunalari

Misol 1 — Linear va binary solishtirish (2.1, 2.2)

const arr = Array.from({ length: 1_000_000 }, (_, i) => i);   // tartiblangan

console.time("linear"); linearSearch(arr, 999_999); console.timeEnd("linear");
console.time("binary"); binarySearch(arr, 999_999); console.timeEnd("binary");
// linear: ~million qadam; binary: ~20 qadam — ulkan farq (3.1)

Misol 2 — Birinchi va oxirgi uchrash (takror — 2.5)

// Takror elementlar orasida birinchi/oxirgi indeks
function birinchiUchrash(arr, x) {
  let chap = 0, ong = arr.length - 1, natija = -1;
  while (chap <= ong) {
    const orta = chap + Math.floor((ong - chap) / 2);
    if (arr[orta] === x) { natija = orta; ong = orta - 1; }  // topdi, lekin chapda davom
    else if (arr[orta] < x) chap = orta + 1;
    else ong = orta - 1;
  }
  return natija;
}
birinchiUchrash([1, 2, 2, 2, 3], 2);   // 1 (birinchi 2)

Misol 3 — Insert position (lower bound — 2.5)

// Saralangan massivga x ni qaysi indeksga qo'yish kerak (tartibni saqlab)
function insertPos(arr, x) {
  let chap = 0, ong = arr.length;
  while (chap < ong) {
    const orta = chap + Math.floor((ong - chap) / 2);
    if (arr[orta] < x) chap = orta + 1;
    else ong = orta;
  }
  return chap;
}
insertPos([1, 3, 5, 7], 4);   // 2 (4 ni 2-indeksga: [1,3,4,5,7])

Misol 4 — Aylantirilgan massivda qidiruv (ilg'or — 2.2)

// Aylantirilgan saralangan massiv [4,5,6,7,0,1,2] da qidiruv (klassik intervyu)
function rotatedSearch(arr, x) {
  let chap = 0, ong = arr.length - 1;
  while (chap <= ong) {
    const orta = chap + Math.floor((ong - chap) / 2);
    if (arr[orta] === x) return orta;
    if (arr[chap] <= arr[orta]) {              // chap yarim saralangan
      if (arr[chap] <= x && x < arr[orta]) ong = orta - 1;
      else chap = orta + 1;
    } else {                                    // o'ng yarim saralangan
      if (arr[orta] < x && x <= arr[ong]) chap = orta + 1;
      else ong = orta - 1;
    }
  }
  return -1;
}
// O(log n) — aylantirilgan bo'lsa ham binary search ishlaydi

5. To'g'ri va noto'g'ri holatlar

1) Tartiblanmagan massivda binary search

//  binary search FAQAT tartiblangan massivda (2.2)
binarySearch([5, 2, 8, 1], 8);   // noto'g'ri natija!

//  avval sarala (yoki linear)
binarySearch([1, 2, 5, 8], 8);

2) < vs <= (chegara xatosi)

//  oxirgi elementni o'tkazib yuboradi (2.2)
while (chap < ong) { ... }   // (oddiy binary search uchun)

//  <= (teng bo'lganda ham tekshir)
while (chap <= ong) { ... }

3) chap = orta (cheksiz tsikl)

//  chap orta'da qoladi  cheksiz tsikl (2.2)
if (arr[orta] < x) chap = orta;

//  orta + 1
if (arr[orta] < x) chap = orta + 1;

4) Bir martalik qidiruv uchun saralash

 tartibsiz massivda bir marta qidirish uchun O(n log n) saralash — isrof
 bir marta  linear O(n); ko'p marta  sort + binary (2.8)

6. Keng tarqalgan xatolar va yechimlari

Xato 1 — Binary search noto'g'ri natija

Sababi: massiv tartiblanmagan (2.2, 1-holat). Yechimi: avval tartiblang; yoki linear ishlating.

Xato 2 — Cheksiz tsikl

Sababi: chap = orta yoki ong = orta (orta o'zgarmaydi — 2.2, 3-holat). Yechimi: orta + 1 / orta - 1 (oddiy variant); lower/upper bound'da ehtiyot 2.5-bob.

Xato 3 — Off-by-one (chegara)

Sababi: < vs <=, length vs length-1 (0.6, 2.2). Yechimi: kichik misolda qo'lda yuring; variant uchun to'g'ri shablon 2.5-bob.

Xato 4 — find/includes katta massivda sekin

Sababi: ular linear O(n) (2.1, 2.8). Yechimi: ko'p qidiruv Set/Map (O(1) — 3.5) yoki sort + binary.

Xato 5 — Topilmaganda -1 ni e'tiborsiz qoldirish

const idx = binarySearch(arr, x);
arr[idx];   // x yo'q bo'lsa idx=-1  arr[-1] = undefined

Sababi: -1 (topilmadi) tekshirilmadi. Yechimi: if (idx !== -1).

7. Integratsiya — bu mavzu stack'ning qayerida uchraydi

• Saralash 3.9-bob: binary search saralangan massivni talab qiladi.
• Big-O 3.1-bob: O(log n) ning eng aniq misoli.
• BST 3.6-bob: binary search g'oyasi daraxtda.
• Hash Table 3.5-bob: muqobil (O(1), tartibsiz).
• Rekursiya 3.11-bob: rekursiv binary search.
• DB indeks 6.9-bob: B-tree — diskda binary search.
• Array metodlari 2.8-bob: includes/find — linear.
• Masala yechish 3.13-bob: binary search on answer 2.7-bob.

8. Eng yaxshi amaliyotlar (best practices)

• Tartiblangan binary (O(log n)); tartibsiz linear yoki Hash 2.8-bob.
• Binary search shablonini to'g'ri yodlang: <=, orta + 1/orta - 1 (2.2, off-by-one).
• orta = chap + (ong - chap) / 2 — overflow-xavfsiz 2.3-bob.
• Topilmadi (-1) ni doim tekshiring (6-bo'lim).
• Ko'p qidiruv bir marta sort + binary, yoki Set/Map 3.5-bob.
• Variantlar (lower/upper bound) — chegara masalalarida 2.5-bob.
• binary search on answer — "min/max shunday X" masalalarida (2.7, 3.13).
• Kunlik ishda includes/find/Set yetadi; binary qo'lda — saralangan katta ma'lumot/maxsus holat.

9. Amaliy loyiha: "Qidiruv Algoritmlari va Variantlari"

Linear va binary search hamda variantlarini amalda mustahkamlash.

Maqsad

Linear va binary search'ni, off-by-one tuzoqlarini va binary search variantlarini (chegara topish) o'zlashtirish.

Talablar (requirements)

1. Linear va binary search: indeks qaytaradi (topilmasa -1) (2.1, 2.2).
2. Vaqt solishtirish: katta tartiblangan massivda ikkalasini o'lchang — O(n) vs O(log n) (Misol 1, 3.1).
3. Rekursiv binary search (Misol/2.4).
4. Birinchi va oxirgi uchrash: takror elementlar orasida (Misol 2, 2.5).
5. Lower/upper bound va insert position (Misol 3, 2.5).
6. Aylantirilgan massivda qidiruv (Misol 4) — ilg'or.
7. Binary search on answer (bonus): "kvadrat ildiz" (sqrt) ni binary search bilan toping 2.7-bob.
8. Chegaraviy holatlar: bo'sh massiv, bitta element, birinchi/oxirgi, yo'q element 0.6-bob.
9. Har birini turli kirishlarda sinab, off-by-one yo'qligini tasdiqlang.

Maslahatlar (hint)

• Binary: while (chap <= ong), orta + 1/orta - 1 (2.2, 5-holat).
• orta = chap + Math.floor((ong - chap) / 2) 2.3-bob.
• Birinchi uchrash: topgach ong = orta - 1 (chapda davom — Misol 2).
• Lower bound: ong = length, while (chap < ong), ong = orta (Misol 3).
• sqrt: javob oralig'i [0, n], orta * orta ni n bilan solishtiring 2.7-bob.
• Topilmadi (-1) ni tekshiring (6-bo'lim).

"Tayyor" mezonlari (acceptance criteria)

• Linear va binary search to'g'ri (topilmasa -1).
• Vaqt solishtirish O(n) vs O(log n) ni ko'rsatadi.
• Rekursiv binary ishlaydi.
• Birinchi/oxirgi uchrash takrorlarni to'g'ri topadi.
• Lower/upper bound va insert position to'g'ri.
• Aylantirilgan massivda qidiruv ishlaydi.
• Barcha chegaraviy holatlar qulamaydi; off-by-one yo'q.

Yechim kodi ataylab berilmagan — bu loyihani o'zingiz yozib ko'ring.

10. Xulosa va keyingi bobga ko'prik

Bu bobda qidiruv algoritmlarini o'rgandik:

• Linear search — birma-bir, O(n), tartiblanmagan (includes/find — 2.8).
• Binary search — tartiblangan massivda, O(log n), yarmiga bo'lish; <=, orta±1 (off-by-one tuzog'i!).
• Variantlar: birinchi/oxirgi uchrash, lower/upper bound, insert position, aylantirilgan massiv.
• Binary search on answer — monoton javob oralig'ida 2.7-bob.
• Qaror: 1 marta linear; ko'p marta sort + binary; tartibsiz Hash 3.5-bob.

Keyingi bob — 3.11-bob: Rekursiya va backtracking. Merge/quick sort 3.9-bob, tree traversal 3.6-bob, DFS 3.7-bob, rekursiv binary search (bu bob) — hammasi rekursiyaga tayanadi. Endi rekursiyani — funksiyaning o'zini chaqirishi — chuqur, va undan o'sib chiqadigan backtracking (barcha variantlarni sinash) ni o'rganamiz.

Foydalanilgan rasmiy/ishonchli manbalar

• bigocheatsheet.com — search algoritmlari murakkabligi (linear O(n), binary O(log n))
• Universal CS — linear/binary search, lower/upper bound, binary search on answer
• MDN Web Docs — Array.prototype.includes/indexOf/find (2.8)