खोज (Searching)

किसी अक्रमित रजिस्टर में अनुक्रमांक ढूँढने का अर्थ है नाम-दर-नाम पढ़ना; शब्दकोश में शब्द ढूँढने का अर्थ है उसे बीच के पास खोलना और हर चरण पर आधी पुस्तक छोड़ देना। पाठ्यक्रम की दो खोज-विधियाँ यही हैं — रैखिक खोज (linear search) और द्विआधारी खोज (binary search) — और उनका अंतर सब कुछ जाँचने और क्रम का उपयोग करने का अंतर है। यह अध्याय दोनों का अनुरेखण करता है, गिनता है कि सबसे अच्छी और सबसे बुरी स्थिति में प्रत्येक को कितनी तुलनाएँ चाहिए, और हैशिंग के साथ समाप्त होता है, जिसका लक्ष्य तत्व को एक ही चरण में पाना है। ऐसे प्रश्नों की अपेक्षा करें जो द्विआधारी खोज में क्रम से जाँचे गए तत्व और सबसे बुरी स्थिति की गिनती पूछें।

रैखिक खोज

रैखिक खोज, जिसे क्रमिक खोज (sequential search) भी कहते हैं, कुंजी की तुलना सूची के हर तत्व से बारी-बारी करती है, पहले से आरंभ करके, जब तक मेल न मिले या अंत न आ जाए। यह क्रम के बारे में कोई मान्यता नहीं रखती, अतः अक्रमित सूची पर काम करती है। कुंजी पहला तत्व हो तो इसे केवल एक तुलना चाहिए — सबसे अच्छी स्थिति। कुंजी अंतिम तत्व हो, या सूची में हो ही नहीं, तो यह कुंजी की तुलना सभी n तत्वों से करती है — सबसे बुरी स्थिति। अतः इसका चलने का समय n के अनुपात में बढ़ता है: यह एक रैखिक एल्गोरिद्म है।

एक रैखिक खोज जो पहले मेल की स्थिति लौटाती है, या कोई न हो तो −1। print(search([5, 3, 5, 8], 5), search([5, 3, 5, 8], 6)) 0 -1 छापता है — दूसरे 5 तक कभी पहुँचा नहीं जाता:
def search(L, key):
for i in range(len(L)):
if L[i] == key:
return i
return -1

द्विआधारी खोज (Binary Search)

द्विआधारी खोज केवल क्रमित सूची पर काम करती है। यह खोजे जाने वाले शेष भाग के चारों ओर दो चिह्नक, first और last, रखती है, और बार-बार मध्य तत्व mid = (first + last) // 2 की जाँच करती है। मध्य तत्व कुंजी के बराबर हो तो खोज सफल। कुंजी छोटी हो तो वह केवल बाएँ आधे में हो सकती है, अतः last बनता है mid − 1; बड़ी हो तो first बनता है mid + 1। जब first, last से आगे निकल जाए, खोजने का भाग ख़ाली है और कुंजी उपस्थित नहीं। हर तुलना शेष का लगभग आधा भाग छोड़ देती है, अतः तुलनाओं की संख्या केवल इस पर बढ़ती है कि n को कितनी बार आधा किया जा सकता है: सबसे बुरी स्थिति में floor(log₂ n) + 1 — 15 तत्वों पर 4, 31 पर 5, 100 पर 7, 1,000 पर 10।

[3, 8, 12, 17, 23, 31, 40] में 23 की द्विआधारी खोज
firstlastmidmid पर तत्वनिर्णय
0631723 > 17, अतः first = 4
4653123 < 31, अतः last = 4
44423सूचकांक 4 पर मिला
⚠️ पूर्णांक भाग बायाँ मध्य चुनता है
first = 4 और last = 5 पर mid है (4 + 5) // 2 = 4, न 4.5 न 5। सम लंबाई वाले भाग में दो मध्य तत्वों में से बायाँ जाँचा जाता है, और ऊपर की ओर पूर्णांकन करने वाला अनुरेखण उस बिंदु से ग़लत तत्व बताएगा।
रैखिक और द्विआधारी खोज की तुलना
विशेषतारैखिक खोजद्विआधारी खोज
सूची क्रमित होनी चाहिए?नहींहाँ
सबसे अच्छी स्थिति1 तुलना (पहला तत्व)1 तुलना (मध्य तत्व)
सबसे बुरी स्थिति, n तत्वn तुलनाएँfloor(log₂ n) + 1 तुलनाएँ
वृद्धिn में रैखिकn में लघुगणकीय

हैशिंग द्वारा खोज

हैशिंग किसी तत्व को दूसरों से तुलना किए बिना ही पाने का प्रयास करती है। हैश फ़ंक्शन स्वयं तत्व से हैश टेबल में वह स्थान निकालता है जहाँ उसे रखा जाना चाहिए। एक सरल फ़ंक्शन शेषफल विधि है: h(element) = element % तालिका का आकार। 10 स्थानों की तालिका में 34 स्थान 4 पर, 16 स्थान 6 पर और 93 स्थान 3 पर जाता है; 93 खोजने के लिए 93 % 10 = 3 निकालें और सीधे स्थान 3 देखें। जब दो तत्व एक ही स्थान दें — 34 और 54 दोनों 4 देते हैं — तो वह टकराव (collision) है, जिसे किसी और नियम से सुलझाना पड़ता है; जो हैश फ़ंक्शन किसी दिए तत्व-समूह के लिए कभी टकराव न दे, वह पूर्ण हैश फ़ंक्शन (perfect hash function) है।

मुख्य बिंदु

  • रैखिक खोज तत्वों को एक-एक कर जाँचती है, अक्रमित सूचियों पर काम करती है, और सबसे अच्छी स्थिति में 1 तथा सबसे बुरी में n तुलनाएँ लेती है।
  • द्विआधारी खोज को क्रमित सूची चाहिए: मध्य से तुलना करें, फिर केवल वह आधा रखें जिसमें कुंजी हो सकती है।
  • mid = (first + last) // 2; छोटी कुंजी पर last = mid − 1, बड़ी पर first = mid + 1, और first > last का अर्थ है नहीं मिला।
  • द्विआधारी खोज को अधिकतम floor(log₂ n) + 1 तुलनाएँ चाहिए: 31 तत्वों पर 5, 1,000 पर 10।
  • हैशिंग तत्व का स्थान सीधे निकालती है, जैसे element % तालिका-आकार; एक स्थान पर दो तत्व टकराव है।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. क्रमित सूची [3, 8, 12, 17, 23, 31, 40] में 23 खोजने के लिए mid = (first + last) // 2 के साथ द्विआधारी खोज प्रयोग की जाती है। किन तत्वों की तुलना 23 से, क्रम में, होती है?

    1. 17, 23
    2. 17, 31, 23
    3. 3, 8, 12, 17, 23
    4. 17, 40, 31, 23
    उत्तर देखें

    उत्तर: B — 17, 31, 23

    पहला mid सूचकांक 3, तत्व 17; 23 बड़ा है, अतः first = 4। अब mid = (4 + 6) // 2 = 5, तत्व 31; 23 छोटा है, अतः last = 4। फिर mid = 4, तत्व 23 — तीन तुलनाओं के बाद मिला। 17, 23 दाएँ आधे के मध्य को छोड़कर सीधे कुंजी पर कूद जाता है। पाँच तत्वों वाला अनुक्रम रैखिक खोज करती, और द्विआधारी खोज में कुछ भी पहले अंतिम तत्व को नहीं देखता।

  2. यह कोड क्या छापता है?
    def search(L, key):
    for i in range(len(L)):
    if L[i] == key:
    return i
    return -1
    print(search([5, 3, 5, 8], 5), search([5, 3, 5, 8], 6))

    1. 2 -1
    2. 1 -1
    3. 0 None
    4. 0 -1
    उत्तर देखें

    उत्तर: D — 0 -1

    लूप पहला मेल मिलते ही लौट जाता है, जो 5 के लिए सूचकांक 0 पर है; सूचकांक 2 वाले 5 तक कभी पहुँचा नहीं जाता। 6 के लिए लूप बिना मेल समाप्त होता है और फ़ंक्शन -1 लौटाता है। 2 उत्तर मानता है कि खोज अंतिम मेल तक चलती है, 1 स्थितियाँ 1 से गिनता है, और None तभी लौटता जब अंतिम return -1 न होता।

  3. किसी सूची पर द्विआधारी खोज विश्वसनीय रूप से लगाने से पहले उसके बारे में क्या सत्य होना चाहिए?

    1. वह क्रमित होनी चाहिए
    2. उसमें कोई दोहराया मान नहीं होना चाहिए
    3. उसकी लंबाई 2 की घात होनी चाहिए
    4. उसमें केवल पूर्णांक होने चाहिए
    उत्तर देखें

    उत्तर: A — वह क्रमित होनी चाहिए

    आधा भाग छोड़ना तभी सुरक्षित है जब मध्य के एक ओर हर तत्व छोटा और दूसरी ओर हर तत्व बड़ा हो, और यही क्रमबद्धन सुनिश्चित करता है। दोहराए मान विधि को नहीं रोकते; यह बस बराबर मानों में से एक को पा लेती है। कोई भी लंबाई चलती है, क्योंकि पूर्णांक भाग हर बार एक मध्य चुन लेता है, और वर्णक्रम में लगी स्ट्रिंगें भी संख्याओं की तरह ही खोजी जा सकती हैं।

  4. 31 तत्वों की क्रमित सूची में कोई कुंजी है या नहीं, यह तय करने के लिए द्विआधारी खोज को अधिकतम कितनी तुलनाएँ चाहिए?

    1. 31
    2. 16
    3. 5
    4. 6
    उत्तर देखें

    उत्तर: C — 5

    हर तुलना शेष तत्वों में से अधिकतम आधे छोड़ती है: 31, फिर 15, 7, 3 और 1, अतः पाँचवीं तुलना के बाद जाँचने को कुछ नहीं बचता — floor(log₂ 31) + 1 = 5। इकतीस रैखिक खोज की सबसे बुरी स्थिति है, जो क्रम की अनदेखी करती है। 16 केवल एक बार आधा करता है, और 6 एक अतिरिक्त चरण जोड़ता है जिसकी 31 के भाग को कभी आवश्यकता नहीं होती।

  5. निम्नलिखित कोड द्वारा क्या छापा जाता है?
    L = [2, 4, 6, 8, 10, 12, 14]
    first, last, steps = 0, len(L) - 1, 0
    key = 5
    while first <= last:
    mid = (first + last) // 2
    steps += 1
    if L[mid] == key:
    break
    elif key < L[mid]:
    last = mid - 1
    else:
    first = mid + 1
    print(steps)

    1. 2
    2. 3
    3. 7
    4. 4
    उत्तर देखें

    उत्तर: B — 3

    चरण 1: mid = 3, तत्व 8; 5 < 8, अतः last = 2। चरण 2: mid = 1, तत्व 4; 5 > 4, अतः first = 2। चरण 3: mid = 2, तत्व 6; 5 < 6, अतः last = 1। अब first (2), last (1) से अधिक है, कुंजी के बिना लूप समाप्त होता है, और steps 3 है। 2 पर रुकना भूलता है कि भाग [2, 2] अभी जाँचना बाक़ी है, और 7 रैखिक खोज की तरह हर तत्व गिनता है।

  6. n तत्वों की सूची पर ऐसी कुंजी के लिए रैखिक खोज चलाई जाती है जो सूची में नहीं है। वह कितनी तुलनाएँ करती है?

    1. 1
    2. n / 2
    3. n
    4. लगभग log₂ n
    उत्तर देखें

    उत्तर: C — n

    रैखिक खोज हर तत्व से तुलना करने के बाद ही निष्कर्ष निकाल सकती है कि कुंजी अनुपस्थित है, अतः असफल खोज में सभी n तुलनाएँ लगती हैं — सबसे बुरी स्थिति। एक तुलना सबसे अच्छी स्थिति है, जब कुंजी संयोग से पहली हो। n / 2 उपस्थित कुंजी का औसत है, और log₂ n क्रमित सूची पर द्विआधारी खोज का है।

  7. अभिकथन (A): रैखिक खोज ऐसी सूची पर प्रयोग की जा सकती है जिसके तत्व किसी विशेष क्रम में न हों। कारण (R): सबसे बुरी स्थिति में रैखिक खोज कुंजी की तुलना सूची के हर तत्व से करती है।

    1. A और R दोनों सत्य हैं, और R, A की सही व्याख्या है
    2. A और R दोनों सत्य हैं, पर R, A की सही व्याख्या नहीं है
    3. A सत्य है, पर R असत्य है
    4. A असत्य है, पर R सत्य है
    उत्तर देखें

    उत्तर: B — A और R दोनों सत्य हैं, पर R, A की सही व्याख्या नहीं है

    दोनों कथन सत्य हैं, पर R रैखिक खोज की लागत बताता है, यह नहीं कि वह अक्रमित डेटा पर क्यों काम करती है। वह किसी भी सूची पर इसलिए काम करती है कि किसी तत्व को छोड़ने के लिए क्रम का कभी उपयोग नहीं करती — मेल मिलने तक हर तत्व बारी-बारी से जाँचा जाता है। "R, A की व्याख्या है" चुनना उन दो सत्य तथ्यों को जोड़ना है जो संयोग से एक ही विधि के बारे में हैं; पेपर ठीक यही जोड़ी यह परखने के लिए रखता है कि संबंध वास्तविक है या नहीं।

  8. पहले तत्व से रैखिक खोज का प्रयोग करते हुए सूची [4, 7, 9, 2] में 9 ढूँढने के लिए कितनी तुलनाएँ चाहिए?

    1. 2
    2. 4
    3. 1
    4. 3
    उत्तर देखें

    उत्तर: D — 3

    कुंजी की तुलना 4, फिर 7, फिर 9 से होती है, जहाँ मेल मिलता है और खोज रुक जाती है: तीन तुलनाएँ। दो, 9 का शून्य-आधारित सूचकांक है, एक स्थिति, गिनती नहीं। चार तभी लगतीं जब कुंजी अंतिम या अनुपस्थित होती, और एक तभी जब वह पहला तत्व होती।