|
-§. Binary Search(Ikkilik qidirish) algoritmi va uning xossalari
|
| bet | 6/12 | | Sana | 21.05.2024 | | Hajmi | 117,25 Kb. | | #248931 |
Bog'liq 1-kurs kurs ishi(2)
— (eng: Binary search— ikkilik qidirish)- saralangan elementlar roʻyxatidan elementni topish uchun samarali algoritm. Ikkilik qidirish algoritmi ishlash gʻoyasiga koʻra „boʻlib tashla va hukmronlik qil paradigma asosida ishlaydi. Ikkilik qidiruvdan foydalanishning eng keng tarqalgan usullaridan biri bu massivdagi elementni topishdir. Misol uchun, Tycho-2 yulduzlar katalogida bizning gallaktikamizdagi eng yorqin 2 539 913 ta yulduz haqida maʼlumot mavjud. Aytaylik, siz yulduz nomidan kelib chiqib, katalogdan maʼlum bir yulduzni qidirmoqchisiz. Agar dastur yulduzlar katalogidagi har bir yulduzni birinchisidan boshlab, chiziqli qidiruv algoritmida tekshirgan boʻlsa, eng yomon holatda kompyuter siz izlayotgan yulduzni topish uchun barcha 2 539 913 ta yulduzni tekshirishi kerak boʻlishi mumkin. Agar katalog yulduz nomlari boʻyicha alifbo tartibida tartiblangan boʻlsa, ikkilik qidiruv, hatto eng yomon holatda ham 22 dan ortiq yulduzni tekshirishi shart emas edi.
Binary Search (Ikkilik qidirish) algoritmi ma'lum bir qiymatni o'lchamli va tartiblangan to'plamda (masalan, massivda yoki ro'yxatda) qidirish uchun ishlatiladi. Bu algoritm odatda tartiblangan to'plamlar uchun foydalaniladi. Ushbu algoritmni bajarish jarayoni quyidagicha:
Boshlang'ich to'plamda o'rta elementni tanlash.
Tanlangan o'rta elementni ma'lum qidiruv qiymatiga solishtirish.
Agar qidirilayotgan qiymat tanlangan o'rta elementdan kichik bo'lsa, qidiruvni o'lchamning bosh qismida davom ettirish.
Agar qidirilayotgan qiymat tanlangan o'rta elementdan katta bo'lsa, qidiruvni o'lchamning oxirgi qismida davom ettirish.
Agar qidirilayotgan qiymat tanlangan o'rta elementga teng bo'lsa, topildi deb hisoblash.
Agar qidiruvni oxirigacha yetib kelgan bo'lsa va topilmagan bo'lsa, topilmagan deb hisoblash.
Binary Search algoritmi ikkilik qidirishga asoslanganligi uchun o'lchamli tartiblangan to'plamlarda ishlash uchun idealdir. Bu algoritmning qo'llanishi quyidagi xossalarga ega:
Tezlik: Binary Search algoritmi to'plamning o'lchamiga bog'liq ravishda tez ishlaydi. To'plamning o'lchami (n) bo'ylab natijani topishning vaqti O(log n) bo'ladi. Buning sababi har bir solishtirish jarayoni to'plamni o'lchamini n/2, n/4, n/8, ... qilib o'chirib boradi.
|
| |
