Ikkitomonlama Izlash - eng oson yo'llaridan biri bir qator bir elementni topish

Ko'pincha, dasturchilar, hatto yangi boshlanuvchilar, ma'lum bir qator topish kerak raqamlari to'plamidir, bor, deb aslida bilan duch keldi. Bu to'plam bir array deb ataladi bo'ladi. Va unda ma'lumotlar topish, yo'llar ko'p bor. Lekin ularning ko'plari oddiy o'ng ikkilik qidiruv ko'rib chiqilishi mumkin. Bu usul nima? Va qanday qilib ikkitomonlama Izlash amalga oshirish uchun? Paskal bunday dasturining bajarilishini tashkil etish uchun eng oson muhit, shuning uchun biz o'rganish uchun foydalanishingiz olaman.

Birinchidan, tahlil, bu usulning afzalliklari bor, u shuning uchun biz tushunish mumkin emas, mavzu o'rganishga nuqtasi nima. Shunday qilib, uning ba'zi topish kerak kamida 100000000 elementlar, bir o'lchov bilan qator bor qilaylik. Albatta, bu muammo osongina biz qator bo'layotganlar bilan zarur elementi solishtirish qiladi tsikli foydalanayotgan bo'lgan oddiy chiziqli qidiruv tomonidan hal qilinishi mumkin. muammo, bu g'oya amalga oshirish juda ko'p vaqt talab etadi. bir necha davolash va asosiy matn uch satrlar oddiy Paskal dasturi, siz uni sezmay, lekin biz filiallari va yaxshi faoliyati bir qator bilan ko'proq yoki kamroq yirik loyihalar kelsalar, dastur ham uzoq ko'targuvchi tayyor bo'ladi. Ayniqsa, kompyuter zaif tomosha bo'lsa. Shuning uchun, eng kamida ikki marta Qidiruv vaqti kamaytiradi ikkilik qidirish, bor.

Shunday qilib, bu usul ish printsipi nima? Darhol u ikkilik qidiruv biron qator emas, balki faqat raqamlar tartib to'plami ishlaydi, deb aytish kerak. qator har bir qadam qabul o'rta element At (element sonini ma'no). zarur bo'lsa soni kattaroqdir o'rtacha, keyin barcha qolgan bo'lsa, bu o'rtacha hujayra kamroq, tashlanadi mumkin va u erda qarash emas. Aksincha, o'rtacha kamroq bo'lsa - o'ng o'sha raqamlar orasida, siz qidirish mumkin emas. So'ngra birinchi element, butun qator o'rta element, va oxirgi va oxirgi irodasi bo'ladi yangi qidiruv maydoni, tanlang. yangi maydon o'rtacha soni, barcha segment, (oxirgi element + butun qator o'rta element) / 2 ¼ bo'ladi. Yana, shu operatsiyani amalga oshiriladi - qator o'rtacha soni bilan taqqoslash. maqsad qiymati o'rtacha kam bo'lsa, biz o'ng tomonini rad, va shuningdek, hozir bu o'rta element kerakli emas edi qadar, keyingi qilish.

Albatta, bu ikki tomonlama qidirish yozish uchun qanday bir misol qarash yaxshi emas. Paskal bu yerda hech kimni mos bo'ladi - versiyasi muhim emas. ning oddiy dastur yozaylik.

Bu ism "massiv" ostida soat 1, bir qator bo'lib, "verh", o'rtacha qidiruv muddatli chaqirdi "niz" deb nomlangan Izlash quyi chegarasini ko'rsatuvchi bir o'zgaruvchi, yuqori chegarasi, - "sredn"; va zarur soni - "ISK".

Shunday qilib, birinchi biz qator qidiruv yuqori va quyi chegarasi yuklansin:

niz: = 1;
verh: = h + 1;

So'ngra "pastki yuqori sonidan kam qadar" tsikli tashkil:

niz boshlash

Har qadamda, biz segmentini 2 ajratish:

sredn: = (niz + verh) div 2; {Qolgan holda bo'l, chunki, vazifasi div foydalaning}

ko'rib chiqish har safar. o'rta orzu bo'lsa element allaqachon qildi, chunki, tsikli to'xtatib:

іf sredn = ISK keyin sindirish;

Kerakli ortiq qator o'rta element, chap tomonini tashlab bo'lsa, ya'ni, o'rtacha yuqori chegara elementi tayinlaydi:

Agar massiv [sredn]> ISK keyin verh: = sredn;

Va aksincha, agar, u pastki chegarasi qiladi:

boshqa niz: = sredn;
tugatish;

Bu dasturda bo'ladi hammasi.

AQSh bu amalda ikkilik usuli qanday ko'rinishini ko'rib chiqaylik. 1, 3, 5, 7, 10, 12, 18 va 12-sonli intiladi: bu qator ko'rib chiqaylik.

Jami biz 7 elementlari bor, shuning uchun to'rtinchi o'rta, qiymati 7 bo'ladi.

dan ortiq, 12, 7, 1,3 va 5 elementlar buyon, biz tashlab mumkin. Keyin, biz sonini 4 bor, 4/2 hech qoldiq 2. Bas, yangi element 10 o'rtacha bo'ladi.

12 10 dan katta bo'lgani, biz 7. faqat 10, 12 va 18-qolmoqda tashlamoq.

Bu erda, o'rta element allaqachon 12, u zarur soni. Bu vazifa bajarildi - qator 12 topildi.