Qidirish (chiziqli, binar)
Massivda biror qiymat bor-yo'qligini yoki u qayerda ekanini aniqlash — eng tez-tez bajariladigan amallardan biri. Foydalanuvchi brauzerda sahifadan matn qidiradi. Elektron do'kon mahsulot bazasidan tovar izlaydi. Tartiblash algoritmi o'z ichida elementning to'g'ri joyini topadi. Bularning barchasi tagida qidiruv algoritmi turadi.
Qidiruv algoritmini tanlashda bir savol hal qiluvchi ahamiyat kasb etadi: massiv saralangan (tartibli)mi yoki saralanmagan (tasodifiy tartibda)mi? Agar saralanmagan bo'lsa, biz faqat bitta ishonchli yo'lni bilamiz — barcha elementlarni birma-bir tekshirish. Agar saralangan bo'lsa, ancha aqlliroq yo'l bor — har safar qidiruv maydonining yarmini tashlab yuborish.
Chiziqli qidiruv — linear search
G'oya
Chiziqli qidiruv (linear search) massivning boshidan boshlab har bir elementni kerakli qiymat bilan taqqoslaydi. Mos element topilganda to'xtaydi; massiv tugaguncha topilmasa, "mavjud emas" deb xabar beradi.
Bu yondashuv hech qanday oldindan tayyorgarlik talab qilmaydi — massiv saralangan bo'lishi shart emas, elementlar bir xil turda bo'lishi ham shart emas. Shu sababli u eng universal qidiruv usuli.
Algoritm
FUNCTION linear_search(array, kerakli_qiymat)
FOR i = 0 DAN array uzunligi - 1 GACHA
IF array[i] = kerakli_qiymat
RETURN i
RETURN -1
-1 — element topilmaganini bildiruvchi shartli qiymat. Ko'pgina muhitlarda "mavjud emas" holatini ifodalash uchun ishlatiladi.
Bosqichma-bosqich tahlil
[15, 7, 42, 3, 28] ichidan 3 qidiramiz:
Index: 0 1 2 3 4
+---+---+---+---+---+
|15 | 7 |42 | 3 |28 |
+---+---+---+---+---+
↑
i = 0: 15 = 3? Yo'q
Index: 0 1 2 3 4
+---+---+---+---+---+
|15 | 7 |42 | 3 |28 |
+---+---+---+---+---+
↑
i = 1: 7 = 3? Yo'q
Index: 0 1 2 3 4
+---+---+---+---+---+
|15 | 7 |42 | 3 |28 |
+---+---+---+---+---+
↑
i = 2: 42 = 3? Yo'q
Index: 0 1 2 3 4
+---+---+---+---+---+
|15 | 7 |42 | 3 |28 |
+---+---+---+---+---+
↑
i = 3: 3 = 3? Ha → RETURN 3
Natija: index 3.
Endi 99 qidiramiz — massivda yo'q:
Murakkablik
Eng yaxshi holat — O(1): Kerakli element massivning birinchi katagi — 0-indexda turadi. Bitta taqqoslash yetadi. Bu kamdan-kam va tasodifiy holat.
Eng yomon holat — O(n): Kerakli element massivning oxirida turadi yoki umuman mavjud emas. Barcha n ta element tekshiriladi.
O'rtacha holat — O(n): Tasodifiy taqsimlangan elementlarda kerakli qiymat o'rtacha n/2-pozitsiyada bo'ladi. Bu O(n/2), ya'ni Big O tahlilida konstantani olib tashlasak, O(n).
Big O tahlilida biz eng yomon holatni asosiy mezon sifatida olamiz, shu sababli linear search O(n) deyiladi.
Xotira murakkabligi — O(1): Qo'shimcha xotira ishlatilmaydi — faqat bitta i indeks o'zgaruvchisi.
Qachon linear search to'g'ri tanlov?
- Massiv saralanmagan bo'lsa — boshqa tanlov yo'q.
- Massiv kichik bo'lsa — 10-50 element orasida linear search qo'shimcha tayyorgarliksiz ishlaydi.
- Qidiruv juda kamdan-kam bajarilsa — massivni saralash uchun sarflangan vaqt tejamga arzimaydi.
- Faqat bitta marta qidirish kerak bo'lsa — massivni saralashga vaqt sarflash mantiqsiz.
Note
Ko'pincha linear search "sekin" deb salbiy baholanadi. Aslida u o'z vazifasini ado etadi. Muammo paydo bo'ladigan joy — millionlab elementli massivda har soniyada ming marta qidiruv bajarilsa. Bunday holatda saralash yoki hash table kabi boshqa tuzilmalarni ko'rish kerak.
Binar qidiruv — binary search
G'oya
Siz lug'atdan so'z qidiryapsiz. Lug'at alifbo tartibida — ya'ni saralangan. Siz uni boshidan varaqlashni boshlamaysiz. O'rtasini ochasiz. Qidirgan so'zingiz o'rtadan oldinmi yoki keyinmi — aytib berasiz. Shundan keyin faqat kerakli yarmi bilan davom etasiz. Shu yarmining o'rtasini ochasiz. Yana yarmini tashlab yuborasiz. Va hokazo.
Bu binary search — binar qidiruv. U har bosqichda qidiruv maydonini yarmiga kamaytiradi. Shu sababli u saralangan massivlarda chiziqli qidiruvga qaraganda ancha tez ishlaydi.
Muhim shart
Binary search faqat saralangan massivda to'g'ri ishlaydi. Saralanmagan massivda u noto'g'ri natija beradi yoki umuman ishlamaydi. Sababi — u har safar "kerakli qiymat o'rtadan kattami yoki kichikmi?" degan savolga javob berib, yarmi tashlab yuboradi. Massiv saralanmagan bo'lsa, bu savol ma'nosiz.
Algoritm
FUNCTION binary_search(array, kerakli_qiymat)
chap = 0
o'ng = array uzunligi - 1
WHILE chap <= o'ng
o'rta = chap + (o'ng - chap) / 2
IF array[o'rta] = kerakli_qiymat
RETURN o'rta
ELSE IF array[o'rta] < kerakli_qiymat
chap = o'rta + 1
ELSE
o'ng = o'rta - 1
RETURN -1
o'rta = chap + (o'ng - chap) / 2 formulasiga e'tibor bering. Ko'rinishdan (chap + o'ng) / 2 ham bir xil natija beradi. Lekin chap + o'ng qiymati juda katta bo'lib, butun son chegarasidan (integer overflow) oshib ketishi mumkin. Shu sababli ushbu xavfsiz formula ishlatiladi.
Bosqichma-bosqich tahlil
[3, 7, 12, 18, 25, 31, 42, 56] ichidan 25 qidiramiz.
1-qadam:
2-qadam:
3-qadam:
3 bosqichda topildi. Linear search 5 ta taqqoslash bajargan bo'lardi.
Endi 10 qidiramiz — massivda yo'q:
[3, 7, 12, 18, 25, 31, 42, 56]
1-qadam: o'rta = 3 → 18 > 10 → o'ng = 2
2-qadam: chap=0, o'rta=1 → 7 < 10 → chap = 2
3-qadam: chap=2, o'ng=2, o'rta=2 → 12 > 10 → o'ng = 1
Endi chap (2) > o'ng (1) → WHILE to'xtaydi → RETURN -1
Nima uchun O(log n)?
Har qadamda qidiruv maydoni yarmiga kamayadi:
1-qadam: n ta element
2-qadam: n/2 ta element
3-qadam: n/4 ta element
...
k-qadam: n / 2^k ta element
Algoritm n / 2^k = 1 bo'lganida to'xtaydi. Bu k = log₂(n) qadamdan keyin. Demak, binary search O(log n) qadamda javob beradi.
Amaliy qiymat:
n = 1 000 → taxminan 10 qadam
n = 1 000 000 → taxminan 20 qadam
n = 1 000 000 000 → taxminan 30 qadam
Bir milliard elementda linear search eng yomon holatda milliard taqqoslash bajaradi. Binary search esa 30 ta. Bu farq katta tizimlarda katta ahamiyat kasb etadi.
Loop invarianti — nima uchun to'g'ri ishlaydi?
Algoritm to'g'ri ishlashi uchun har doim quyidagi shart bajarilishi kerak: agar kerakli element massivda bo'lsa, u [chap, o'ng] oralig'ida turadi.
Tashqi WHILE sikli har bosqichda ushbu shartni saqlaydi:
- Agar
array[o'rta] < kerakli_qiymatbo'lsa, kerakli elemento'rtaning o'ng tomonida. Shuning uchunchap = o'rta + 1. - Agar
array[o'rta] > kerakli_qiymatbo'lsa, kerakli elemento'rtaning chap tomonida. Shuning uchuno'ng = o'rta - 1. - Agar
array[o'rta] = kerakli_qiymatbo'lsa — topildi.
chap > o'ng bo'lsa, qidiruv oralig'i bo'shliq — kerakli element massivda yo'q.
Bu qat'iy mantiq binary searchning to'g'ri ishlash kafolati.
Birinchi va oxirgi holatni topish
Ba'zan massivda bir xil qiymat bir necha marta takrorlanadi. Standart binary search ulardan istalgan bittasini topadi. Ko'pincha esa birinchi yoki oxirgi uchrashuv kerak bo'ladi.
Birinchi uchrashuv:
FUNCTION birinchi_uchrashuv(array, kerakli_qiymat)
chap = 0
o'ng = array uzunligi - 1
natija = -1
WHILE chap <= o'ng
o'rta = chap + (o'ng - chap) / 2
IF array[o'rta] = kerakli_qiymat
natija = o'rta
o'ng = o'rta - 1 ← chap tomonga davom etamiz
ELSE IF array[o'rta] < kerakli_qiymat
chap = o'rta + 1
ELSE
o'ng = o'rta - 1
RETURN natija
Element topilganda natijaga saqlaymiz, lekin to'xtatmaymiz — yana chap tomonga qarab ketamiz. Oxirida natija birinchi uchrashuv indexini saqlagan bo'ladi.
Oxirgi uchrashuv uchun xuddi shu mantiq, faqat element topilganda chap = o'rta + 1 qilinadi — o'ng tomonga davom etiladi.
Qayerga kiritish kerak? — insertion point
Yana bir foydalanish holati: saralangan massivda yangi element kira oladigan joyni topish. Bu, masalan, yangi qiymatni tartibni buzmasdan qo'shishdan oldin kerak bo'ladi.
FUNCTION insertion_point(array, qiymat)
chap = 0
o'ng = array uzunligi
WHILE chap < o'ng
o'rta = chap + (o'ng - chap) / 2
IF array[o'rta] < qiymat
chap = o'rta + 1
ELSE
o'ng = o'rta
RETURN chap
Bu funksiya qiymat qo'shilganda tartibni saqlash uchun element joylashishi kerak bo'lgan indexni qaytaradi.
Murakkablik
| Holat | Vaqt murakkabligi | Izoh |
|---|---|---|
| Eng yaxshi | O(1) |
Birinchi o'rtada kerakli element |
| O'rtacha | O(log n) |
|
| Eng yomon | O(log n) |
Element topilmasa ham log n qadam |
| Xotira murakkabligi | O(1) |
Faqat bir nechta o'zgaruvchi |
Ikkala algoritmni taqqoslash
| Xususiyat | Linear search | Binary search |
|---|---|---|
| Saralash talabi | Yo'q | Ha, albatta |
| Eng yomon holat | O(n) |
O(log n) |
| Kichik massivda | Tez | Tez |
| Katta massivda | Sekin | Juda tez |
| Takrorlangan elementlar | Birinchisini topadi | Istalganini topadi |
| Xotira | O(1) |
O(1) |
Keng tarqalgan xatolar
Saralanmagan massivda binary search
Bu eng keng tarqalgan xato. Massiv saralanmagan bo'lsa, binary search noto'g'ri natija beradi yoki element hatto massivda bo'lsa ham -1 qaytaradi. Binary searchdan oldin massiv saralanganligi kafolatlanishi kerak.
Sonsiz takrorlash (cheksiz loop)
o'rta = chap + (o'ng - chap) / 2 noto'g'ri hisoblansa yoki chap, o'ng qiymatlari to'g'ri yangilanmasa, algoritm bir joyda "aylanib" qolishi mumkin. chap = o'rta + 1 va o'ng = o'rta - 1 bo'lishiga e'tibor berish kerak — o'rtaning o'zi emas.
O'rtani hisoblashda integer overflow
o'rta = (chap + o'ng) / 2 yozuvida chap + o'ng qiymati butun son chegarasidan oshib ketishi mumkin. chap + (o'ng - chap) / 2 formulasi bundan himoya qiladi.
Noto'g'ri chekka shart
WHILE chap < o'ng va WHILE chap <= o'ng — ikkalasi ham ishlaydi, lekin oralig'ni qanday belgilashga qarab tanlanadi. Agar o'ng = array uzunligi - 1 (yopiq oraliq) bo'lsa, chap <= o'ng to'g'ri. Agar o'ng = array uzunligi (ochiq oraliq) bo'lsa, chap < o'ng ishlatiladi. Bu ikki yondashuvni aralashtirib yuborish noto'g'ri natijaga olib keladi.
Bo'sh massivni unutish
Uzunligi 0 bo'lgan massivda linear search darhol -1 qaytarishi kerak. Binary searchda o'ng = -1 bo'ladi va WHILE chap <= o'ng sharti darhol bajarilmaydi — -1 qaytariladi. Lekin ba'zi implementatsiyalarda bu holat maxsus tekshirilmasa xato yuzaga kelishi mumkin.
Qachon qaysi qidiruvni tanlash kerak?
Linear search tanlang agar: - Massiv saralanmagan va saralash imkoni bo'lmasa; - Qidiruv bir martalik yoki kamdan-kam bo'lsa; - Massiv kichik (50 dan kam element) bo'lsa; - Ma'lumot tuzilmasi index orqali kirishga mos kelmasa (masalan, bog'liq ro'yxat — linked list).
Binary search tanlang agar:
- Massiv saralangan bo'lsa yoki saralash imkoni bo'lsa;
- Bir massivda ko'p marta qidiruv bajarilsa;
- Massiv katta bo'lsa;
- O(log n) — ya'ni katta n uchun keskin farq — muhim bo'lsa.
Tip
Agar bir massivda ko'p marta qidiruv bajarilsa, massivni bir marta saralash (O(n log n)) va keyin har bir qidiruv uchun binary search ishlatish (O(log n)) linear searchdan (O(n) har marta) umumiy jihatdan tezroq bo'ladi. Qancha qidiruv bo'lishi bu qarorni belgilaydi.
Eng muhim xulosa
Qidiruv algoritmi tanlashda birinchi savol har doim bir xil: massiv saralanganmi? Bu savolning javobi ko'plab amaliy qarorlarni belgilaydi.
Linear search — oddiy, universal, har doim to'g'ri ishlaydi. Binary search — kuchli, lekin faqat saralangan massivda. Ikkala algoritmning ham xotirada qo'shimcha joy olmaydi — O(1). Farq faqat vaqtda.
Keyingi qismda massivni saralash algoritmlarini — bubble, selection va insertion sortni — ko'rib chiqamiz: ular qanday ishlaydi, nima uchun O(n²) beradi va qaysi holatlarda ulardan foydalanish to'g'ri keladi.