7-dars: Ikkilik qidiruv

1-darajaBronza — algoritmik fikrlash1–8 darslar

HayotdaLug'at

Qalin lug’atdan «samarador» so’zini qidirayotganingizda birinchi sahifadan boshlamaysiz. Kitobni o’rtasidan ochasiz, harfga qaraysiz va yarmini butunlay tashlab yuborasiz. Ming sahifali lug’at o’nta ochishda tugaydi.

Bu darsdan keyin siz

• saralangan ro’yxatda ikkilik qidiruvni xatosiz yozasiz
• «birinchi mos keladigan o’rin» ni topadigan ko’rinishini bilasiz
• cheksiz sikl paydo bo’ladigan joyni oldindan taniysiz

Avval qo’lda

Avval qo‘lda

~5 daqiqa·juftlikda·Qog'oz va qalam

Sinfdoshingiz 1 dan 1000 gacha son o’ylasin. Siz taxmin aytasiz, u faqat «kattaroq», «kichikroq» yoki «topdingiz» deb javob beradi.

Har savoldan oldin qog’ozga qolgan oraliqni yozib boring: 1–1000, keyin 1–500 va hokazo. Nechta savolda topdingiz?

Nimani sezishingiz kerak

O’nta savol yetdi, chunki har javob oraliqni ikkiga bo’ldi: 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. Birma-bir so’ralganda esa 1000 tagacha savol kerak bo’lardi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Sekin yechim

Kutubxonada kitoblar raqami bo’yicha saralangan. Har so’rovda «shu raqamli kitob bormi va qaysi indeksda?» deb so’raladi. Birinchi yechim — boshidan oxirigacha yurish.

sekin.pyNusxalash

1kitoblar = [2, 5, 5, 8, 12, 16, 23]2def qidir(x):3  for i in range(len(kitoblar)):4      if kitoblar[i] == x:5          return i6  return -17print(qidir(5), qidir(7), qidir(23))

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1kitoblar = [2, 5, 5, 8, 12, 16, 23]2def qidir(x):3  for i in range(len(kitoblar)):4      if kitoblar[i] == x:5          return i6  return -17print(qidir(5), qidir(7), qidir(23))

Sizning bashoratingizTekshirish

Javobni ko'rish

1 -1 6

Yechim to'g'ri ishlaydi, lekin u ro'yxat saralanganini umuman ishlatmaydi — tartibsiz ro'yxatda ham xuddi shunday yurgan bo'lardi.

Nega sekin

Eng yomon holatda har so’rov butun ro’yxatni o’qiydi. n ham, so’rovlar soni q ham 200000 gacha bo’lishi mumkin.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 200 000
Har so‘rovda boshidan yurishn^2	10⁶sig‘adi	10¹⁰sig‘maydi
Ikkilik qidiruvn log n	9 966sig‘adi	10⁶sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Ro’yxat saralangan ekan, biz ancha kuchli savol bera olamiz. «Bu element mi?» emas, «men qidirayotgan son bu elementdan katta mi?» — chunki javob bir zumda yarim ro’yxatni yo’q qiladi.

Tez yechim

ikkilik qidiruvbinary search

Saralangan ro’yxatda qidiruv oralig’ini har qadamda ikkiga bo’lib kichraytirish usuli. n elementda taxminan log₂ n qadam ketadi.

Quyidagi ko’rinish elementni emas, birinchi mos keladigan o’rinni topadi. Bu shakl universal: takrorlangan sonlar bo’lsa ham to’g’ri ishlaydi va «yo’q» holatini alohida ishlashni talab qilmaydi.

tez.pyNusxalash

1kitoblar = [2, 5, 5, 8, 12, 16, 23]2def birinchi_orin(x):3  chap, ong = 0, len(kitoblar)4  while chap < ong:5      orta = (chap + ong) // 26      if kitoblar[orta] < x:7          chap = orta + 18      else:9          ong = orta10  return chap11i = birinchi_orin(5)12print(i)

Sikl chap == ong bo’lganda to’xtaydi va o’sha nuqta javob bo’ladi. Diqqat qiling: ong boshida len(kitoblar) ga teng, ya’ni ro’yxatdan tashqarida — bu «hech qanday element mos kelmadi» holatini tabiiy ifodalaydi.

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1kitoblar = [2, 5, 5, 8, 12, 16, 23]2def birinchi_orin(x):3  chap, ong = 0, len(kitoblar)4  while chap < ong:5      orta = (chap + ong) // 26      if kitoblar[orta] < x:7          chap = orta + 18      else:9          ong = orta10  return chap11i = birinchi_orin(5)12print(i)

Sizning bashoratingizTekshirish

Javobni ko'rish

1

Ikkita beshlik bor, javob esa BIRINCHISINING indeksi. Oddiy ikkilik qidiruv ikkovidan qay birini topishini kafolatlamaydi — shuning uchun shu shakl afzal.

Python’da bu funksiya tayyor holda ham bor. Olimpiadada uni qo’lda yozishni bilish shart, kundalik ishda esa bisect ishlatiladi.

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1from bisect import bisect_left2kitoblar = [2, 5, 5, 8, 12, 16, 23]3print(bisect_left(kitoblar, 5))4print(bisect_left(kitoblar, 7))

Sizning bashoratingizTekshirish

Javobni ko'rish

1
3

7 ro'yxatda yo'q, lekin javob baribir qaytadi: 3 — 7 qo'yilishi kerak bo'lgan o'rin. Element bor-yo'qligini bilish uchun o'sha o'rindagi qiymatni tekshirish kerak.

Sinab ko’r

Vizualda «qolgan» katagini kuzating: 15 → 7 → 3 → 1. Har qadamda qidiruv maydoni yarmiga qisqaradi — ikkilik qidiruvning butun kuchi shu raqamlar ketma-ketligida.

Ikkilik qidiruv — har savolda yarmi ketadi

«Qolgan» katagini kuzating: 15 → 7 → 3 → 1.

Har taqqoslashdan keyin qidirish maydoni ikki barobar kichrayadi: 15 elementga 4 ta savol yetadi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. 72 ni qidiramiz. 15 element, hammasi saralangan. Chap = 0, o'ng = 14.
2. O'rtadagi 45 kichik — 72 undan o'ngda. Chap yarmi butunlay tashlanadi.
3. O'rtadagi 80 katta — 72 undan chapda. O'ng yarmi tashlanadi.
4. O'rtadagi 61 kichik — 72 undan o'ngda. Chap yarmi butunlay tashlanadi.
5. O'rtadagi 72 = 72. Topildi — 4 ta savol bilan.
6. 50 ni qidiramiz. 15 element, hammasi saralangan. Chap = 0, o'ng = 14.
7. O'rtadagi 45 kichik — 50 undan o'ngda. Chap yarmi butunlay tashlanadi.
8. O'rtadagi 80 katta — 50 undan chapda. O'ng yarmi tashlanadi.
9. O'rtadagi 61 katta — 50 undan chapda. O'ng yarmi tashlanadi.
10. O'rtadagi 56 katta — 50 undan chapda. O'ng yarmi tashlanadi.
11. Chap o'ngdan o'tib ketdi — qidirish maydoni bo'shadi. Demak 50 ro'yxatda YO'Q. Buni ham 4 ta savolda bildik.

saralangan

chap2051821231642353864575686197210801191129513o'ng9914

qolgan

element15

72 ni qidiramiz. 15 element, hammasi saralangan. Chap = 0, o'ng = 14.

Savol0

OrqagaO‘ynatishOldinga1/11Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

7 / 40

MasalaSaralangan ro'yxatda x sonini ikkilik qidiruv bilan toping.

Taklif qilingan yechim

1. 1chap = 0, ong = n - 1 deb boshlaymiz.
2. 2Sikl chap <= ong bo‘lguncha davom etadi, orta = (chap + ong) // 2.
3. 3kitoblar[orta] < x bo‘lsa chap = orta, aks holda ong = orta - 1.
4. 4Sikl tugagach x topilmagan bo‘ladi.

Bu javobning 3-qismi noto'g'ri. chap = orta yozilgan — bu chap chegarasini SILJITMAYDI. Ikki element qolganda orta har safar chap ga teng bo'lib chiqadi va sikl abadiy aylanadi. To'g'risi: chap = orta + 1. Har qadamda oraliq albatta kichrayishi shart.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1Million elementli ro'yxatda ikkilik qidiruv nechta qadam qiladi?

Javobni ko'rish

Taxminan 20 ta, chunki log₂(10⁶) ≈ 20. Chiziqli qidiruv esa eng yomon holatda million qadam qilardi.

2Ikkilik qidiruv uchun qanday shart bajarilishi kerak?

Javobni ko'rish

Ro’yxat saralangan bo’lishi. Aniqrog’i: «bu nuqtadan chapda javob yo’q, o’ngda bor» degan xossa saqlanishi kerak. Saralanganlik shu xossaning eng oddiy ko’rinishi.

3ong = len(royxat) deb boshlash nima beradi?

Javobni ko'rish

Element umuman yo’q bo’lsa, javob len(royxat) bo’lib qaytadi — ya’ni «hamma elementdan katta». Bu holatni alohida if bilan ushlash shart emas.

4bisect_left topilmagan sonda nima qaytaradi?

Javobni ko'rish

Xato bermaydi va -1 ham qaytarmaydi: u shu son qo’yilishi kerak bo’lgan o’rinni qaytaradi. Element bor-yo’qligini bilish uchun o’sha indeksdagi qiymatni alohida tekshirish kerak.

5Har qadamda nimani tekshirib turish kerak?

Javobni ko'rish

Oraliq haqiqatan kichrayayotganini. chap yoki ong dan bittasi albatta siljishi shart — aks holda sikl to’xtamaydi.

Masalalar

Masalalar

3 ta

• Interesting drinkCodeforces 706Boson

  Narxlarni saralang, keyin har so‘rovga «nechtasi shu qiymatdan katta emas» deb javob bering.

• WormsCodeforces 474Boson

  Prefiks yig‘indi quring (5-dars), keyin ustidan ikkilik qidiruv yurgizing.

• Concert TicketsCSES 1091o'rta

  Har mijozga narxidan oshmaydigan eng qimmat chiptani bering. Chipta sotilgach ro‘yxatdan olinadi.

Lokal mashq: mashqlar/07-ikkilik-qidiruv/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

1 dan 1000 gacha bo’lgan sonni topish o’yinini uch marta o’ynang va har safar savollar sonini yozing. Keyin 1 dan 1 000 000 gacha bo’lganda nechta savol kerakligini hisoblang.

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

07-ikkilik-qidiruv masalasini yeching. Yechimingizni ataylab shu uch holatda sinang: bitta elementli ro’yxat, hamma elementlari bir xil ro’yxat, ro’yxatda yo’q son.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

birinchi_orin ni o’zgartirib, oxirgi_orin ni yozing — ya’ni berilgan sondan katta birinchi element indeksi. Ikkalasini birlashtirib, sonning ro’yxatda necha marta uchrashini bitta log n da toping.

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim