«amaliy matematika va informatika» kafedrasi «Algoritmlar nazariyasi» fanidan Mustaqil ish

barcha oldingi raqamlarni (16-raqamdan oldin joylashgan) oʻtkazib yuborish mumkin: ular biz izlayotganimizdan kichikroq boʻlishi aniq, chunki bizning qatorimiz tartiblangan! Qolgan 5 ta element orasida qidirishni davom ettiramiz. Iltimos, biz faqat bitta tekshiruvni amalga oshirdik, ammo allaqachon mumkin boʻlgan variantlarning yarmini bekor qildik. Bizda atigi 5 ta narsa qoldi. Biz qadamimizni takrorlaymiz - qolgan massivni yana 2 ga boʻlinib, yana oʻrta elementni olamiz (rasmdagi 3-satr). Bu raqam 56 ga teng va u biz izlayotgan raqamdan kattaroqdir. Bu nimani anglatadi? Yana uchta variantni - 56 raqamning oʻzi va undan keyingi ikkita raqamni bekor qilishimiz kerak (ular, albatta, 23 dan ortiq, chunki qator tartiblangan). Bizda tekshirish uchun atigi 2 ta raqam qoldi (rasmdagi oxirgi qator) - 5 va 6 qator indekslari boʻlgan raqamlar. Ularning birinchisini tekshiring, va biz qidirgan narsa bu - 23 raqami! Uning indeksi \u003d 5! Keling, algoritmimiz natijalarini koʻrib chiqamiz, keyin biz uning murakkabligi bilan shugʻullanamiz. (Aytgancha, endi nima uchun u ikkilik deb nomlanishini tushunasiz: uning mohiyati maʻlumotlarni doimiy ravishda 2 ga boʻlishida yotadi). Natija ajoyib! Agar biz toʻgʻri raqamni chiziqli qidirish bilan izlayotgan boʻlsak, biz 10 ta tekshiruvga muhtoj boʻlamiz va ikkilik qidiruv bilan biz 3 ga teng boʻldik! Eng yomon holatda, ularning soni 4 ta boʻlar edi, agar oxirgi bosqichda biz kerak boʻlgan raqam birinchi emas, ikkinchisi boʻlib chiqsa. Uning murakkabligi haqida nima deyish mumkin? Bu juda qiziqarli nuqta :) Ikkilik qidiruv algoritmi chiziqli qidirish algoritmiga (yaʻni oddiy sanab chiqishga) qaraganda massivdagi elementlar soniga juda kam bogʻliq. Qachon 10 massivdagi elementlar, chiziqli qidiruv uchun maksimal 10 ta tekshirish, ikkilik qidiruv uchun esa maksimal 4 ta tekshirish kerak boʻladi. Farqi 2,5 baravar. Ammo qator uchun