1. Qidiruv algoritmning òziga xos dasturi. Binar qidiruv algoritmning asosiy ģoyasi. Binar qidiruvining yana bir kòrinishi

Mavzu:Qidirish(izlash)algaritmalri.Binar qidiruv algaritmalri.
Reja:
1.Qidiruv algoritmning òziga xos dasturi.
2.Binar qidiruv algoritmning asosiy ģoyasi.
3.Binar qidiruvining yana bir kòrinishi.

Yilda Kompyuter fanlari, a qidirish algoritmi har qanday algoritm hal qiladigan qidirish muammosi, ya'ni ba'zi ma'lumotlar tarkibida saqlangan yoki ichida hisoblangan ma'lumotlarni olish uchun qidirish maydoni muammo domenining yoki diskret yoki uzluksiz qiymatlar. Qidiruv algoritmlarining o'ziga xos dasturlariga quyidagilar kiradi.

Muammolar kombinatorial optimallashtirish, kabi:
The transport vositasini yo'naltirish muammosi, shakli eng qisqa yo'l muammosi
The xalta muammosi: Har birining vazni va qiymati bo'lgan buyumlar to'plamini hisobga olgan holda, jami og'irlik berilgan chegaradan kichik yoki unga teng bo'lgan va umumiy qiymati iloji boricha katta bo'lishi uchun to'plamga kiritiladigan har bir narsaning sonini aniqlang.
The hamshirani rejalashtirish muammosi
Muammolar qoniqish cheklash, kabi:
The xaritani bo'yash muammosi
To'ldirish a sudoku yoki krossvord
Yilda o'yin nazariyasi va ayniqsa kombinatorial o'yin nazariyasi, keyingi qilish uchun eng yaxshi harakatni tanlash (masalan, bilan minmax algoritm)
Barcha imkoniyatlardan kombinatsiya yoki parolni topish
Faktoring butun son (muhim muammo kriptografiya)
Sanoat jarayonini optimallashtirish, masalan kimyoviy reaktsiya, jarayon parametrlarini o'zgartirish (masalan, harorat, bosim va pH)
A dan yozuvni olish ma'lumotlar bazasi
A-dagi maksimal yoki minimal qiymatni topish ro'yxat yoki qator
Berilgan qiymat qiymatlar to'plamida mavjudligini tekshirishEntsiklopediya site:uz.wikisko.ru



Aytaylik bizga tartiblangan n ta elementdan iborat arr[] massiv berilgan bo'lsin, va berilgan x ni arr[] ichidan qidirish funksiyasini tuzish sharti qo'yilsin.
Bu holatda eng oson yo'l sifatida chiziqli qidiruvni misol keltirish mumkin. Ammo bu usulning vaqt davomiyligi O(n) ni tashkil qiladi. Xuddi shu vazifa uchun biz binar qidir algoritmini ishlatsak bo'ladi.
Binar qidiruv
Qiyinlik darajasi: 5/10.
Eng zo'r ko'rsatkichi(vaqt): O(1)
Eng yomon ko'rsatkichi(vaqt): O(log n)
O'rtacha ko'rsatkichi(vaqt): O( log n)
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.
Masalan:h
Biz bitta taqqoslashdan so'ng massivning yarim elementlarini hisobga olmasak ham bo'ladi.
1. x ni o'rtadagi element bilan solishtiramiz.
2. Agar rost bo'lsa, o'rtadagi elementni qaytaramiz.
3. Agar x katta bo'lsa, x ni massivni o'ng yarmini ichidan qidiramiz, yuqoridagi ketma-ketlikni bajargan holda.
4. Aks holda chap yarmi bilan binar qidiruvni amalga oshiramiz.
Quyida Binar qidiruvning rekursiya orqali amalga oshiramiz.
// C++ tilida rekursiyali Binar Qidiruv
#include
// Rekursiyali qidiruv funksiyasi. U massivdan
// x qaysi o'rinda turganini qaytaradi,
// yoki -1