1. Kirish Binar qidiruv tizimining tarixi
Download 3.55 Mb. Pdf ko'rish
|
1 2
Bog'liqBinar qidiruv
|
Kirish Binar qidirish — (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“ paradigmasi asosida ishlaydi. Ikkilik qidiruvdan foydalanishning eng keng tarqalgan usullaridan biri bu massivdagi elementni topishdir. Misol uchun, Tycho-2 yulduzlar katalogida bizning galaktikamizdagi 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. Binary Search Binar qidirish algoritmi ishlash prinsipi Ikkilik qidirish algoritmining ishlashini tushunish uchun kompyuter bilan oʻyin oʻynab koʻramiz. Oʻyin sharti Kompyuter 1 va 100 oraligʻida ixtiyoriy natural son tanlaydi. Oldimizda turgan vazifa shu sonni iloji boricha kam taxmin ishlatgan holda topish. Har bir taxmindan keyin kompyuter sizga sizning taxminingiz kompyuter tanlagan sondan katta yoki kichikligini aytadi. Agar sizning taxminingiz kompyuter tanlagan son bilan bir xil boʻlsa, oʻyin tugaydi. Buning uchun eng kam qadamda topish algoritmi qaysi? Birinchi navbatda oʻrtadagi sonni taxmin qilib koʻramiz, yaʼni 50 ni. Aytaylik kompyuter bizga taxminimiz kompyuter tanlagan sondan kichikroq ekanligini aytdi. Endi biz kompyuter tanlagan son 51 va 100 orasidagi son ekanligini bilamiz. Shunday qilib, bizning qidirish sohamiz ikki baravarga qisqaradi (50 ta son). Huddi shu tarzda davom etamiz. Endi 51 dan 100 gacha sonlar oʻrtasidagi sonni olamiz, yaʼni 75 ni. Kompyuter bizga 75 tanlangan sondan katta ekanligini aytdi. Demak, 75 dan katta barcha sonlar ham tanlangan sondan katta ekan. Shunday qilib, bizdagi qidirish sohasi yana ikki baravarga qisqardi (25 ta son). Huddi shunday davom etib, biz oʻylangan sonni topishimiz mumkin. Sonlar 100 ta boʻlgan holatda, biz har qanday tahminni koʻpi bilan 7 ta qadamda topishimiz mumkin boʻladi. #include using namespace std; int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; if (arr[mid] == x) return mid; if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); return binarySearch(arr, mid + 1, r, x); } return -1; } int main(void) { int arr[] = { 2, 3, 4, 10, 40 }; int x = 10; int n = sizeof(arr) / sizeof(arr[0]); int result = binarySearch(arr, 0, n - 1, x); (result == -1) ? cout << "Element massivda mavjud emas" : cout << "Element indeksda mavjud " << result; return 0; } Binar qidiruv algoritmi haqida qo’shimcha ma’lumotlar quyidagicha: Binar qidiruv algoritmi, saralangan elementlar ro’yxatidan kerakli elementni topish uchun samarali algoritmlardan biri hisoblanadi1 . Binar qidiruv algoritmi ishlash g’oyasiga ko’ra “bo’lib tashla va hukmronlik qil” paradigmasi asosida ishlaydi1 . Binar qidiruvning asosiy g’oyalaridan biri ketma-ket ikkiga bo’lishga asoslanadi, ya’ni berilgan x ni massivning o’rtadagi elementi bilan solishtiradi, agar katta bo’lsa oxiri va o’rtasi orasidagi massivni oladi, agar kichkina bo’lsa boshi va o’rtasi orasidagi massivni oladi, va har safar shu jarayon takrorlanib boradi toki x element solishtirilayotgan massivning elementga teng bo’lgunicha yoki massivning elementlari qolmaguncha Binar qidiruv algoritmi, massivdan elementni topish uchun eng keng tarqalgan usullardan biri hisoblanadi2 . Binar qidiruv algoritmi, rekursiya yoki iterativ usulda ham yozish mumkin3 . Binar qidiruv algoritmi, vaqt davomiyligi O(log n) ni tashkil qiladi1 . Quyida C++ tilida binar qidiruv algoritmini rekursiyali va interative usullar bilan yozilgan misollari keltirilgan1 Rekursiyali usul: #include int binarqidiruv(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; if (arr[mid] == x) return mid; if (arr[mid] > x) return binarqidiruv(arr, l, mid - 1, x); return binarqidiruv(arr, mid + 1, r, x); } return -1; } int main(void) { int arr[] = {2, 3, 4, 10, 40}; int n = sizeof(arr) / sizeof(arr[0]); int x = 10; int natija = binarqidiruv(arr, 0, n - 1, x); (natija == -1) ? printf("X soni massivni ichidan topilmadi.") : printf("X soni massivning %d - elementi.", natija); return 0; } Interative usul: #include int binarqidiruv(int arr[], int l, int r, int x) { while (l <= r) { int m = l + (r - l) / 2; if (arr[m] == x) return m; if (arr[m] < x) l = m + 1; else r = m - 1; } return -1; } int main(void) { int arr[] = {2, 3, 4, 10, 40}; int n = sizeof(arr) / sizeof(arr[0]); int x = 10; int natija = binarqidiruv(arr, 0, n - 1, x); (natija == -1) ? printf("X soni massiv ichida topilmadi.") : printf("X soni massivning %d o'rnida.", natija); return 0; } Bu kodlar, berilgan massiv ichidan x sonini topish uchun binar qidiruv algoritmini amalga oshiradi . Binar qidiruv algoritmi, saralangan elementlar ro’yxatidan elementni topish uchun samarali algoritmlardan biri hisoblanadi1 . Binar qidiruv algoritmi ishlash g’oyasiga ko’ra “bo’lib tashla va hukmronlik qil” paradigmasi asosida ishlaydi1 . Binar qidiruvning asosiy g’oyalaridan biri ketma-ket ikkiga bo’lishga asoslanadi, ya’ni berilgan x ni massivning o’rtadagi elementi bilan solishtiradi, agar katta bo’lsa oxiri va o’rtasi orasidagi massivni oladi, agar kichkina bo’lsa boshi va o’rtasi orasidagi massivni oladi, va har safar shu jarayon takrorlanib boradi toki x element solishtirilayotgan massivning elementga teng bo’lgunicha yoki massivning elementlari qolmaguncha Binar qidiruv algoritmi, massivdan elementni topish uchun eng keng tarqalgan usullardan biri hisoblanadi2 . Misol uchun, Tycho-2 yulduzlar katalogida bizning galaktikamizdagi 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, binar qidiruv, hatto eng yomon holatda ham 22 dan ortiq yulduzni tekshirishi shart emas edi Download 3.55 Mb. Do'stlaringiz bilan baham: 
|
1 2