Qidirish algoritmlari: chiziqli va ikkilik

Qidirish — to‘plamda kerakli elementni topish yoki uning yo‘qligini aniqlash. Eng sodda usul — chiziqli qidirish: elementlar boshidan birin-ketin tekshiriladi va topilganda to‘xtatiladi. U har qanday ro‘yxatda ishlaydi, lekin eng yomon holatda barcha n ta elementni ko‘rib chiqishga to‘g‘ri keladi. Python’da ro‘yxat uchun x in a yoki a.index(x) aynan shunday ishlaydi.

Ikkilik qidirish faqat saralangan massivda ishlaydi. U kerakli sonni o‘rtadagi element bilan solishtiradi: kerakli son kichik bo‘lsa, o‘ng yarmi tashlab yuboriladi, katta bo‘lsa — chap yarmi. Qolgan qismda jarayon takrorlanadi, shuning uchun har qadamda qidiruv sohasi taxminan ikki baravar qisqaradi. O‘rtadagi indeks mid = (low + high) // 2 formulasi bilan topiladi.

Saralangan 2 5 8 12 16 23 38 56 72 91 massivda 23 ni qidiraylik. 1-qadamda o‘rtadagi 16 kerakli sondan kichik, shuning uchun qidiruv o‘ng yarmida (23 38 56 72 91) davom etadi. 2-qadamda o‘rtadagi 56 katta, demak, chap qismi (23 38) qoladi; 3-qadamda o‘rtadagi element 23 ga teng — son topildi.

Chiziqli qidirishda solishtirishlar soni elementlar soniga mutanosib, ikkilik qidirishda esa ko‘pi bilan taxminan log2 n ta. Masalan, 1 000 000 ta elementli saralangan massivda ikkilik qidirish ko‘pi bilan 20 qadam bajaradi, chiziqli qidirish esa million tagacha solishtirish qiladi. Biroq massivni avval saralash kerak bo‘lsa, bitta qidirish uchun chiziqli usul oddiyroq; ko‘p marta qidirilganda esa bir marta saralab, keyin ikkilik usuldan foydalanish foydali.

Asosiy xulosalar

• Chiziqli qidirish elementlarni birin-ketin tekshiradi va har qanday ro‘yxatda ishlaydi.
• Ikkilik qidirish faqat saralangan massivda ishlaydi.
• Ikkilik qidirish har qadamda qidiruv sohasini taxminan ikki baravar qisqartiradi.
• 1 000 000 elementda ikkilik qidirish ko‘pi bilan 20 qadam, chiziqli qidirish esa million tagacha solishtirish bajaradi.
• Ko‘p marta qidirishdan oldin massivni bir marta saralab qo‘yish foydali.