Blok-sxemasi: Boshlash
N,A[N], X
i=1,..,N / A[i]≠X
1:Tamom
Yo’q 1
+/- Bor
Binar(ikkilik) qidiruv.
Bu usul binar qidiruvni iterativ usuli deyiladi, shuningdek bu algoritmni rekursiya usulida ham yozish mumkin, rekursiv usulni erinmasangiz o'zingiz yozib ko'ring. Bitta urinishda ko'pchilik dasturchilar bu narsani to'g'ri yoza olishmaydi va bu normal holat, chunki xato bor joyda o'z ustida ishlash uchun imkoniyat bo'ladi.
Endi bu qidiruv usullarini ayrim jihatlarini keltirib o'tamiz:
funksiyaga berilayotgan massiv Binar qidiruv uchun albatta o'sish(kamayish) tartibida bo'lishi talab qilinadi, chiziqli qidiruv uchun esa berilayotgan massiv qay tartibda bo'lishini ahamiyati yo'q
chiziqli qidiruvda elementlarni bittalab har birini tekshiriladi, binarda esa algoritmidan kelib chiqib chiziqliga nisbatan ancha kam solishtirish amali bajariladi, chiziqli qidiruvning ishlash vaqti ko'pi bilan O(n) va binar qidiruvniki ko'pi bilan O(log n).
12.1 Rekursiv xisoblashlar masalasi uchun algoritmlar va ularning murakkabligini aniqlash.
Юқорида қайд қилингандек рекурсия деб функция танасида шу функциянинг ўзини чақиришига айтилади. Рекурсия икки хил бўлади:
оддий – агар функция ўз танасида ўзини чақирса;
воситали – агар биринчи функция иккинчи функцияни чақирса, иккинчиси эса ўз навбатида биринчи функцияни чақирса.
Одатда рекурсия математикада кенг қўлланилади. Чунки аксарият математик формулалар рекурсив аниқланади. Мисол тариқасида факториални ҳисоблаш формуласини
ва соннинг бутун даражасини ҳисоблашни кўришимиз мумкин:
Кўриниб турибдики, навбатдаги қийматни ҳисоблаш учун функциянинг «олдинги қиймати» маълум бўлиши керак
12.2 Qidirish algoritmlari. Ikkilik(Binary) qidirish algoritmi.
Ikkilik qidirish — Ο(log n) vaqti murakkabligi bilan tezkor qidiruv algoritmi. Ushbu qidirish algoritmi boʻlinish (divide) va yengish (conque) prinsipi asosida ishlaydi. Ushbu algoritm toʻgʻri ishlashi uchun maʼlumotlar toʻplanishi tartiblangan shaklda boʻlishi kerak.
Ikkilik qidirish toʻplamning koʻp qismini oʻrtasini taqqoslash orqali maʼlum bir narsani qidiradi. Agar mos kelsa, unda element indeksi qaytariladi. Agar oʻrta qism elementdan kattaroq boʻlsa, u holda ushbu element oʻrta qismning chap tomonidagi pastki qatorda qidiriladi. Aks holda, element oʻrta elementning pastki qismidagi pastki qatorda qidiriladi. Ushbu jarayon pastki massivda, shuningdek sub-massivning kattaligi nolga tushguncha davom etadi.
Dostları ilə paylaş: |
