binary search algoritmlari

DOCX 13 sahifa 88,1 KB Bepul yuklash

13 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 88,1 KB

Fayl turi DOCX

Sahifalar 13

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 13

mavzu 8: linear va binary search algoritmlari 1. binary search algoritmlari. 2. linear algoritmlari. qidirish algoritmlarini solishtiramiz binary search tasavvur qiling siz ingliz-o'zbek lug'atidan "programming" so'zining tarjimasini qidirayapsiz. siz ingliz alifbosidagi harflar tartibini bilasiz, shuning uchun lug'atni o'rtarog'idan ochib qaraysiz (p harfi lug'at o'rtasiga yaqin). yana bir misol, siz googleda yangi sariqdev@gmail.com akkauntini ochmoqchisiz. google siz istagan akkaunt band yoki yo'qligini tekshirishi kerak (balki sizdan avval kimdur bu akkauntni band qilib bo'lgandur). demak, google o'zidagi akkauntlar ro'yxatidan siz kiritgan akkauntni qidirib ko'radi. buning oson yo'li ro'yxat boshidan boshlab, siz istagan akkauntni barcha mavjud akkauntlar bilan solishtirib chiqish, lekin ro'yxat o'rtasidan boshlab tekshirish mantiqan to'g'ri bo'ladi. yuqoridagi usul (ro'yxat yoki lug'at o'rtasidan boshlash) binary search (ikkilik qidiruvi) deyiladi. binary search ishlashi uchun ro'yxat tartiblangan bo'lishi shart! nima uchun binary search? keling quyidagi miolni ko'ramiz: men 1 dan 100 gacha son o'yladim (deylik 30), siz bu sonni topishingiz kerak. agar ro'yxat boshidan …

2 / 13

adi. keling endi binary search qanday ishlashini ko'ramiz. men yana 30 sonini o'yladim. sizning birinchi savolingiz "50 sonini o'yladingmi?" bo'ladi. men "yo'q, kichikroq" deb javob qilaman va siz bemalol 50 dan katta sonlarni tashlab yuborasiz. 1-qadamdayoq ro'yxatimiz 2 barobar qisqardi va sizda 1-50 sonlar ro'yxati qoldi. siz yana ro'yxat o'rtasidagi sonni so'raysiz: "25 sonini o'yladingmi?" bu safar men "yo'q, kattaroq" deb javob qilaman, va bu safar siz ro'yxatning 1-yarmini tashlab yuborasiz (1-25) va ikkinchi yarmining (25-50) o'rtasidan so'raysiz. va hokazo to to'g'ri sonni topgunga qadar shu zaylda davom etasiz va 30 sonini 6-qadamda topasiz. endi tasavur qiling, siz 40000 so'zdan iborat lug'atdan biror so'zni qidirayapsiz. agar soz lug'at so'ngida bo'lsa (eng so'nngi so'z) chiziqli qidiruv 40000 qadamdan, binary search esa 15 qadamdan iborat bo'ladi xolos. agar lug'at tarkibini ikki barobar ko'paytrisak (80000) so'z, chiziqli qidiruv qadamlari ham 2 barobar oshadi, binary search esa bor yo'gi 1 qadamga (16 qadam) oshadi …

3 / 13

gan ro'yxat va boshqalar) algoritmlar faqat kerakli elementni topish uchun qo'llaniladigan metodologiyada farqlanadi. farqlarni tushunishdan oldin, keling, har bir qidiruvni alohida ko'rib chiqaylik. linear search linear searchchiziqli qidiruv massivning har bir elementini kerakli element aniqlanmaguncha ketma-ket tekshiradi. natijada, eng yomon vaqt murakkabligi tartibdir�(�)o ( n )chunki elementni qidirish uchun talab qilinadigan vaqt elementlar soniga proportsionaldir. /// linear search psedocode while (element_found = false and counter element_required) right = counter - 1 else display(list[counter]) chiziqli va ikkilik qidiruvning skanerlash usullari ikkala qidiruv ham ma'lumotlar to'plamining tabiatiga qarab turli xil afzallik va kamchiliklarga ega. biz asosiy farqlarni quyidagicha aniqlashimiz mumkin: · amalga oshirish: chiziqli qidiruv har qanday chiziqli ma'lumotlar tuzilmasida amalga oshirilishi mumkin. ikkilik qidiruv ikki tomonlama o'tishga ega ma'lumotlar tuzilmalarini talab qiladi. · saralangan ma'lumotlar: chiziqli qidiruv ma'lumotlarni saralash uchun hech qanday talabga ega emas. ikkilik qidiruv faqat tartiblangan ma'lumotlarda amalga oshirilishi mumkin. · samaradorlik: ikkilik qidiruv, ayniqsa kattaroq ma'lumotlar to'plamlari …

4 / 13

gilangan qiymatning o'rnini topishga qaratilgan yondashuvdir. ikkilik qidiruv - chiziqli massivdagi elementning o'rnini topish uchun ishlatiladigan eng tez va samarali qidiruv usuli. ikkilik qidiruv faqat tartiblangan massivlarda qo'llanilishi mumkin. ikkilik qidiruv uchun ma'lumotlar birinchi navbatda saralanishi kerak va agar ma'lumotlar raqamlar shaklida bo'lsa, o'sish tartibida yoki satrlar formatida bo'lsa, alifbo tartibida (a dan z gacha) tartibga solinishi kerak. saralanmagan shakldagi ma'lumotlar massivida ikkilik qidiruvni qo'llash uchun avval o'sish tartibida saralash jarayoni va keyin ikkilik qidiruvni qo'llash orqali saralanishi kerak. ushbu texnikada massivni birinchi navbatda tartiblash kerak, so'ngra izlash jarayoni massivni ikkiga bo'lish orqali o'rta nuqtani topishga asoslangan. ikkilik qidiruvning asosiy maqsadi o'rta nuqtani qidirishdir. agar birinchi tekshirishda kerakli element topilmasa, massiv xuddi shu protsedurani takrorlash orqali ko'proq kichik massivlarga bo'linadi. ikkilik qidirish qiyinligi massivdagi ko'proq sonli elementlar bilan ortadi. ikkilik qidiruv odatda logarifmik qidiruv yoki yarim intervalli qidiruv sifatida tan olinadi. ikkilik qidiruvning ishlash printsipi uning ishlash printsipi " bo'l …

5 / 13

endi biz massivning o'rta elementini topamiz. chunki biz massivni ikkiga bo‘lish uchun uning o‘rta o‘rnini topmoqchimiz. buning uchun chap qiymat 'a' va o'ng qiymat ' l ' deylik . massivda. shunday qilib, formula quyidagicha bo'ladi: keyin saralangan ro'yxatdagi o'rta element bilan qidiruv elementlari o'rtasida taqqoslash amalga oshiriladi. faraz qilaylik, agar 'x' massivda qidiruv elementi bo'lsa, unda uchta holat bo'ladi. 1-holat: agar ikkala element mos kelsa/topilgan bo'lsa, " berilgan element topildi " ni ko'rsating va funktsiyani tugating 2-holat: agar kerakli qidiruv elementi o'rta elementdan kichikroq bo'lsa, o'rta elementning chap pastki ro'yxati uchun yuqoridagi protsedurani yana bajaring. 3-holat: agar kerakli qidiruv elementi o'rta elementdan kattaroq bo'lsa, o'rta elementning o'ng pastki ro'yxati uchun yuqoridagi jarayonni yana bajaring. keyinchalik, shunga o'xshash jarayon biz kerakli qidiruv elementiga etib borgunimizcha takrorlanadi. agar element qidiruv elementiga ham mos kelmasa, " element ro'yxatda topilmadi " ni ko'rsating. misol ikkilik qidiruv tushunchasini tushunish uchun yana bir misolni ko'rib chiqaylik. …

Ko'proq o'qimoqchimisiz?

Barcha 13 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"binary search algoritmlari" haqida

mavzu 8: linear va binary search algoritmlari 1. binary search algoritmlari. 2. linear algoritmlari. qidirish algoritmlarini solishtiramiz binary search tasavvur qiling siz ingliz-o'zbek lug'atidan "programming" so'zining tarjimasini qidirayapsiz. siz ingliz alifbosidagi harflar tartibini bilasiz, shuning uchun lug'atni o'rtarog'idan ochib qaraysiz (p harfi lug'at o'rtasiga yaqin). yana bir misol, siz googleda yangi sariqdev@gmail.com akkauntini ochmoqchisiz. google siz istagan akkaunt band yoki yo'qligini tekshirishi kerak (balki sizdan avval kimdur bu akkauntni band qilib bo'lgandur). demak, google o'zidagi akkauntlar ro'yxatidan siz kiritgan akkauntni qidirib ko'radi. buning oson yo'li ro'yxat boshidan boshlab, siz istagan akkauntni barcha mavjud akkauntlar bilan solishtirib chiqish, le...

Bu fayl DOCX formatida 13 sahifadan iborat (88,1 KB). "binary search algoritmlari"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: binary search algoritmlari DOCX 13 sahifa Bepul yuklash Telegram