Linear कि binary search?
16 वटा सङ्ख्यामा दुई तरिकाले खोज्नुहोस्: एक-एक गरेर, र हरेक चरणमा सूचीलाई आधा गरेर। हरेकलाई कति पटक तुलना चाहिन्छ दाँज्नुहोस्, अनि नमिलाइएको सूचीमा binary search चलाएर त्यहाँ भएको सङ्ख्या पनि नभेटेको हेर्नुहोस्।
मूल अवधारणा
Binary search ले खोजेको सङ्ख्यालाई मिलाइएको सूचीको बीचको वस्तुसँग तुलना गरेर, त्यो हुन नसक्ने आधा भाग फाल्छ, त्यसैले 16 वटा वस्तुमा 16 पटकको सट्टा बढीमा 5 पटक तुलना चाहिन्छ; यो मिलाइएको input मा मात्र चल्छ
पाठ: Algorithm
शब्दकोशमा कुनै शब्द खोज्ने कुरा सोच्नुहोस्। तपाईं हरेक पाना पढ्नुहुन्न: बीचमा खोल्नुहुन्छ, शब्द पछाडि आउँछ भनेर देख्नुहुन्छ, र दोस्रो आधामा मात्र हेर्नुहुन्छ, अनि फेरि आधा गर्नुहुन्छ। यही Binary: 0 र 1 दुई अङ्क मात्र प्रयोग गरेर गन्ने तरिका। कम्प्युटरले सबै कुरा यसरी राख्छ। सबै मुख्य शब्द search हो। यसले low देखि high सम्मको झ्याल राख्छ, बीचको वस्तु (mid) हेर्छ, र खोजेको सङ्ख्या ठूलो भए low लाई mid + 1 मा सार्छ; सानो भए high लाई mid − 1 मा सार्छ। हरेक तुलनाले बाँकीको आधा भाग फाल्छ, त्यसैले 16 वटा वस्तुमा बढीमा 5 पटक, र दस लाखमा करिब 20 पटक मात्र तुलना चाहिन्छ। तर सर्त: हो वा होइन उत्तर हुने प्रश्न, जसले Program ले अब के गर्ने भनेर छुट्याउँछ। सबै मुख्य शब्द छ: सूची मिलाइएको (sorted) हुनुपर्छ, नत्र फालिएको आधामा खोजेको सङ्ख्या हुन सक्छ। Linear search लाई क्रम चाहिँदैन तर हरेक वस्तु हेर्नुपर्ने हुन सक्छ।
के सिक्नुहुनेछ
- low, high र mid सहित binary search trace गर्नुहोस्।
- एउटै सङ्ख्याका लागि linear र binary search को तुलना गन्ती दाँज्नुहोस्।
- Binary search लाई किन मिलाइएको सूची चाहिन्छ, व्याख्या गर्नुहोस्।
- दिइएको आकारको सूचीमा binary search लाई बढीमा कति पटक तुलना चाहिन्छ, अनुमान गर्नुहोस्।
सुरु गर्नुअघि
- Linear search र सूचीका index थाहा हुनुपर्छ।
सामग्री
- तुलनाको सङ्ख्या लेख्न कापी
उपकरण
- केही पनि चाहिँदैन
विधि
- मिलाइएको सूचीमा 60 का लागि linear search चलाएर तुलना गन्नुहोस्।
- उही सङ्ख्याका लागि binary search मा बदलेर दाँज्नुहोस्।
- नमिलाइएको सूचीमा binary search चलाएर के हुन्छ हेर्नुहोस्।
- अभ्यासका challenge को उत्तर दिनुहोस्।