Haqiqiy ikkilik qidiruv

ALGORITM VA MA'LUMOTLAR STRUKTURASI FANIDAN Haqiqiy ikkilik qidiruv MAVZUSIDA TAYYORLAGAN KURS ISHI TAQDIMOTI Reja: Kirish I.Asosiy qism 1.1. Graflar va ularning tasvirlanishi 1.2. Daraxt va ularni turlari 1.3. Haqiqiy ikkilik qidruv algoritmi 1.4. C++ dasturlash tilida ikkilik qidruv II. Xulosa IV. Foydalanilgan adabiyotlar ro'yxati KIRISH Qidiruv vazifasi dasturlashda eng keng tarqalgan vazifalardan biridir.Shuningdek, u ko'rib chiqilayotgan narsaning qo'llanilishini namoyish qilish uchun ajoyib imkoniyatdir. Qidiruv tizimi hamma sohada ishlatilishi sababli ma'lumotlar tuzilmalari kompyuterda bajarish ancha oson bo'ladi. Kompyuterda ma'lumotlarni topish maqsadida maxsus kod kiritilgan kompyuterga shu bilan bir qatorda global qidiruv tizimida ham huddi shu maqsadda va shunga o'xshash kod kiritilgan. Graflar va ularning tasvirlanishi Graflar nazariyasi haqida umumiy ma'lumotlar. 1736 yilda L. Eyler tomonidan o'sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko'priklari haqidagi masalaning qo'yilishi va yechilishi graflar nazariyasining paydo bo'lishiga asos bo'ldi. XIX asrning o'rtalarida graflar nazariyasi bilan bog'liq tadqiqotlar G. Kirxgof va A. Keli ishlarida paydo bo'ldi. Graf iborasi D. Kyonig tomonidan 1936 yilda graflar nazariyasiga bag'ishlangan dastlabki darslikda uchraydi. Graflar nazariyasi bo'yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo'llaniladi. Ulardan ba'zilari quyidagilardir: boshqotirmalarni hal qilish; qiziqarli o'yinlar; yo'llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirish; avtomatlar, blok-sxemalar va komp'yuter uchun programmalarni tadqiq qilish va hokazo. Daraxt va ularni turlari Ikkilik qidiruv daraxti (BST), shuningdek, buyurdi yoki saralangan ikkilik daraxt, a ildiz otgan ikkilik daraxti uning ichki tugunlari har birida tugmachaning chap pastki daraxtidagi barcha tugmachalardan kattaroq va uning o'ng pastki daraxtidagi tugmachalardan kichikroq kalit saqlanadi. Ikkilik daraxt - bu bir turi ma'lumotlar tuzilishi raqamlar kabi ma'lumotlarni uyushgan ravishda saqlash uchun. Ikkilik qidiruv daraxtlari imkon beradi ikkilik qidiruv tezkor qidirish, ma'lumotlar elementlarini qo'shish va olib tashlash uchun va amalga oshirish uchun ishlatilishi mumkin dinamik to'plamlar va qidiruv jadvallari. Ikkilik daraxtning ta'rifi Ikkilik daraxt - bu daraxt tugunlari uchun eng ko'p ikkita ko'rsatgichga ega bo'lgan daraxt tuzilishi. Bu shuni anglatadiki, tugunning eng yuqori darajasi 2 ga teng va u yerda nol yoki bir darajali tugun ham bo'lishi mumkin. Ikkilik qidiruv ishlaydi logaritmik vaqt ichida eng yomon holat, qilish taqqoslashlar, qaerda - bu massivdagi elementlar soni. Ikkilik qidiruv tezroq chiziqli qidiruv kichik massivlardan tashqari. Biroq, ikkilik qidiruvni amalga oshirish uchun birinchi navbatda qatorni saralash kerak. Haqiqiy ikkilik qidruv algoritmi Haqiqiy ikkilik qidiruv Haqiqiy ikkilik qidiruv (inglizcha Bisection usuli ) - monotonik haqiqiy funksiyaning berilgan qiymati uchun argumentni topish algoritmi. Keling, ikkilikqidiruv g'oyasini qo'llaymiz . funksiyaning qiymati berilgan qiymatdan aynan katta va to'liq kichik bo'lgan shunday chegaralarni tanlaylik. Keling, ...