होम › मुफ़्त नोट्स › कक्षा 12 कंप्यूटर विज्ञान › सर्चिंग

सर्चिंग – कक्षा 12 कंप्यूटर विज्ञान नोट्स, महत्वपूर्ण प्रश्न और MCQ

NCERT कक्षा 12 कंप्यूटर विज्ञान, अध्याय 6। नोट्स, मुख्य शब्द, उत्तर सहित महत्वपूर्ण प्रश्न और MCQ।

अध्याय का सार

Searching यह पता लगाने की प्रक्रिया है कि दिया गया element, जिसे key कहते हैं, किसी संग्रह में है या नहीं और यदि है तो उसकी स्थिति क्या है। इस अध्याय में linear search, binary search और hashing द्वारा search शामिल हैं। Linear search किसी भी list पर कार्य करता है, binary search को sorted list चाहिए पर यह बहुत तेज़ है, और hashing, hash function और hash table का प्रयोग कर constant time में element खोज सकता है।

Linear और binary search

Linear (sequential) search key की शुरू से प्रत्येक element से तुलना करता है जब तक वह न मिले या list समाप्त न हो; best case में 1 तुलना, worst case में n तुलनाएँ चाहिए, इसलिए यह O(n) है।
Binary search sorted list पर कार्य करता है: key की middle element से तुलना करें; बराबर हो तो search समाप्त; छोटा हो तो बायाँ आधा खोजें; बड़ा हो तो दायाँ आधा खोजें; मिलने तक या range ख़ाली होने तक दोहराएँ।
Binary search हर चरण में search space आधा करता है, इसलिए अधिकतम लगभग log₂n तुलनाएँ, O(log n), लेता है; 1,024 elements हेतु अधिकतम 11 तुलनाएँ चाहिए।

Hashing

Hashing hash function से hash table में element की स्थिति सीधे निकालता है, जैसे h(element) = element % table का आकार।
Search हेतु key पर वही hash function लगाकर केवल उस स्थान की जाँच की जाती है, जो आदर्श स्थिति में constant time O(1) लेता है।
Collision तब होता है जब दो elements एक ही स्थान पर map होते हैं; collision resolution तकनीकें इसे सँभालती हैं, और perfect hash function प्रत्येक element को अद्वितीय स्थान पर map करता है।

मुख्य शब्द

Searching: किसी संग्रह में key है या नहीं और कहाँ है, यह खोजना
Linear search: आरंभ से एक-एक कर elements की जाँच
Binary search: key खोजने हेतु sorted list को बार-बार आधा करना
Hash function: element की storage स्थिति निकालने वाला function
Collision: दो elements का एक ही स्थान पर hash होना

उत्तर सहित महत्वपूर्ण प्रश्न

Binary search, linear search से तेज़ क्यों है?2 अंक

Binary search key की middle element से तुलना करता है और हर चरण में शेष elements का आधा हटा देता है, इसलिए तुलनाओं की संख्या log n के रूप में बढ़ती है। Linear search को प्रत्येक element जाँचना पड़ सकता है, इसलिए तुलनाएँ n के रूप में बढ़ती हैं। पर binary search को sorted list चाहिए।

Linear search हेतु Python function लिखिए।3 अंक

def linear_search(L, key): for i in range(len(L)): if L[i] == key: return i; फिर loop के बाद return -1। Key मिलने पर यह उसका index लौटाता है, अन्यथा -1।

Binary search को उसके algorithm और उदाहरण सहित समझाइए।5 अंक

Binary search sorted list में key खोजने की कुशल विधि है। यह तीन variables का प्रयोग करता है: low (आरंभ index), high (अंत index) और mid। Algorithm: low = 0 और high = n - 1 रखें; जब तक low <= high: mid = (low + high) // 2 निकालें; यदि L[mid] == key, तो key mid पर मिली; यदि L[mid] < key, तो key केवल दाएँ आधे में हो सकती है, इसलिए low = mid + 1 रखें; अन्यथा high = mid - 1 रखें। Key मिले बिना loop समाप्त हो तो वह उपस्थित नहीं है। Python: def binary_search(L, key): low, high = 0, len(L) - 1; while low <= high: mid = (low + high) // 2; if L[mid] == key: return mid; elif L[mid] < key: low = mid + 1; else: high = mid - 1; फिर return -1। उदाहरण: [5, 9, 14, 23, 31, 42, 56] में 23 खोजें। चरण 1: low = 0, high = 6, mid = 3, L[3] = 23, जो key के बराबर है, इसलिए एक तुलना में मिल गया। 42 खोजने हेतु: mid = 3, 23 < 42, इसलिए low = 4; mid = (4 + 6) // 2 = 5, L[5] = 42, मिल गया। प्रत्येक तुलना search space आधा करती है, इसलिए binary search linear search के O(n) की तुलना में O(log n) समय लेता है, जिससे यह बड़ी sorted lists हेतु बहुत तेज़ है।

त्वरित पुनरावृत्ति

Linear search और उसकी complexity।
Binary search के चरण और complexity।
Hashing, hash table, hash function।
Collisions।

परीक्षा सुझाव

Binary search के लिए sorted list आवश्यक है।
प्रत्येक चरण में mid = (low + high) // 2 का अनुरेखण करें।

अभ्यास MCQ

आरंभ से एक-एक कर प्रत्येक element की जाँच है
1. binary search
2. linear search
3. hashing
4. sorting
उत्तर देखें
उत्तर: (b) linear search. यह unsorted lists पर कार्य करता है।
Binary search केवल किस पर लगाया जा सकता है
1. unsorted list
2. sorted list
3. केवल dictionary
4. केवल string
उत्तर देखें
उत्तर: (b) sorted list. यह क्रम पर निर्भर है।
Hash table में दो elements का एक ही स्थान पर map होना कहलाता है
1. match
2. collision
3. pass
4. swap
उत्तर देखें
उत्तर: (b) collision. इसका समाधान आवश्यक है।
n elements हेतु linear search में worst-case तुलनाओं की संख्या है
1. n
2. 1
3. log n
4. n/2
उत्तर देखें
उत्तर: (a) n. Key अंतिम या अनुपस्थित हो सकती है।
Binary search की time complexity है
1. O(log n)
2. O(n)
3. O(n²)
4. O(1)
उत्तर देखें
उत्तर: (a) O(log n). Search space हर बार आधा होता है।
h(x) = x % 10 का प्रयोग करने पर element 47 किस स्थान पर store होता है
1. 7
2. 4
3. 47
4. 0
उत्तर देखें
उत्तर: (a) 7. 47 % 10 = 7।
[3, 8, 12, 17, 25, 31, 40] पर key 31 हेतु binary search में पहला जाँचा गया middle element है
1. 12
2. 17
3. 25
4. 31
उत्तर देखें
उत्तर: (b) 17. mid = (0 + 6) // 2 = 3, element 17।
1,000 elements हेतु binary search को अधिकतम लगभग कितनी तुलनाएँ चाहिए
1. 1000
2. 10
3. 100
4. 500
उत्तर देखें
उत्तर: (b) 10. 2 की घात 10 = 1,024।

सभी अध्याय: कक्षा 12 कंप्यूटर विज्ञान

यह सामग्री Kundali IQ ने पुनरावृत्ति में मदद हेतु मानक, स्थापित तथ्यों से लिखी है। यह NCERT का आधिकारिक प्रकाशन नहीं है; अपनी पाठ्यपुस्तक भी अवश्य पढ़ें।