17-ma’ruza. Qidiruv va saralash

Misol 1

Top 6 {-1 5 6 18 19 25 46 78 102 114} ichidan.

Qadam 1 (markaziy element 19>6): -1 5 6 18 19 25 46 78  102 114

Qadam 2 (markaziy element 5<6): -1 5 6 18 19 25 46 78  102 114

Qadam 3 (markaziy element 6=6): -1 5 6 18 19 25 46 78  102 114
Misol 2

Top 103 {-1 5 6 18 19 25 46 78  102 114} ichidan.

Qadam 1 (markaziy element 19<103): -1 5 6 18 19 25 46 78  102 114

Qadam 2 (markaziy element 78<103): -1 5 6 18 19 25 46 78  102 114

Qadam 3 (markaziy element 102<103): -1 5 6 18 19 25 46 78  102 114

Qadam 4 (markaziy element 114<103): -1 5 6 18 19 25 46 78  102 114

Qadam 5 (qidirilayotgan element yo`q): -1 5 6 18 19 25 46 78  102 114
Umumiy analiz

Bu algaritmning yahshi tamoni u massiv o`lchamni lagarifmi bilan bog`liq xolda eng yamon holatda joylashganda topa olishidadir. Amalyotda buning ma`nosi algoritm iterasiya jarayonlari soni ning qiymatidan oshmaydi va bu juda kichik son bo`ladi agar biz katta o`lchamli masssivlar ichidan izlaganda ham. Algoritm juda sodda ko`rinishga ega. Albatta, qidirilayotgan o`lchamdagi har bir qadam yarim oraliq orqali izlanadi. Algoritm to`xtaydi, agar qidirilayotgan element yo`q bo`lsa yoki topilsa. Quyidagi tngsizlik yechimni topish zarur.

Natija

Bundan kelib chiqadiki binariy qidirish usuli bilan hisoblaniar ekan.

BinarySearch algaritmini bir nicha ullar bilan yozib ko`rsatamiz.