सर्चिंग — अध्ययन नोट्स

1. परिचय

सर्चिंग (Searching) का अर्थ है किसी डेटा संग्रह में से एक विशिष्ट तत्व (लक्ष्य) को खोजना। जब हम किसी सूची में किसी विशेष संख्या, स्ट्रिंग या रिकॉर्ड को खोजना चाहते हैं तो हम सर्चिंग एल्गोरिथ्म का उपयोग करते हैं। सर्चिंग कंप्यूटर विज्ञान की सबसे सामान्य क्रियाओं में से एक है, चाहे वह फोन बुक में नाम खोजना हो, ईमेल में कोई संदेश खोजना हो या डेटाबेस में कोई रिकॉर्ड ढूंढना हो।

सर्चिंग के दो मुख्य एल्गोरिथ्म हैं: रैखिक सर्च (Linear Search) और बाइनरी सर्च (Binary Search)। रैखिक सर्च किसी भी सूची (सॉर्टेड या असॉर्टेड) पर कार्य करती है, जबकि बाइनरी सर्च के लिए सूची का सॉर्ट होना अनिवार्य है। बाइनरी सर्च रैखिक सर्च से अधिक तेज़ होती है, परंतु केवल सॉर्ट किए गए डेटा पर।

2. रैखिक सर्च (Linear Search)

रैखिक सर्च सबसे सरल खोज विधि है। इसमें हम सूची के पहले तत्व से प्रारंभ करके क्रमशः प्रत्येक तत्व की तुलना लक्ष्य तत्व से करते हैं। जैसे ही लक्ष्य मिलता है, हम उसकी स्थिति (index) लौटाते हैं। यदि पूरी सूची में तत्व नहीं मिलता तो उचित संदेश लौटाया जाता है। यह विधि सॉर्टेड और असॉर्टेड दोनों सूचियों पर कार्य करती है।

def linear_search(lst, target):
    for i in range(len(lst)):
        if lst[i] == target:
            return i
    return -1

numbers = [10, 23, 45, 70, 11, 15]
result = linear_search(numbers, 70)
print("तत्व अनुक्रमांक:", result)   # 3

result2 = linear_search(numbers, 99)
print("तत्व अनुक्रमांक:", result2)  # -1 (नहीं मिला)

रैखिक सर्च की जटिलता:

• सर्वश्रेष्ठ स्थिति: O(1) (लक्ष्य पहले तत्व पर हो)
• सबसे खराब स्थिति: O(n) (लक्ष्य अंतिम तत्व पर या अनुपस्थित हो)
• औसत स्थिति: O(n)
• स्थान जटिलता: O(1)

रैखिक सर्च का उपयोग तब उचित है जब सूची छोटी हो या असॉर्टेड हो, या जब हम केवल कुछ ही बार खोज करना चाहते हैं।

3. बाइनरी सर्च (Binary Search)

बाइनरी सर्च एक अधिक कुशल खोज विधि है जो विभाजित और जीत (Divide and Conquer) सिद्धांत पर कार्य करती है। इसके लिए सूची का सॉर्ट होना अनिवार्य है। इस विधि में हम बार-बार सूची के मध्य (middle) तत्व की तुलना लक्ष्य से करते हैं:

1. मध्य तत्व की गणना करें: mid = (low + high) // 2
2. यदि मध्य तत्व लक्ष्य के बराबर है तो mid लौटाएँ।
3. यदि मध्य तत्व लक्ष्य से बड़ा है तो बाईं ओर के भाग में खोजें (high = mid - 1)।
4. यदि मध्य तत्व लक्ष्य से छोटा है तो दाईं ओर के भाग में खोजें (low = mid + 1)।
5. यह प्रक्रिया तब तक चलती है जब तक low <= high। यदि लक्ष्य नहीं मिलता तो -1 लौटाएँ।

def binary_search(lst, target):
    low = 0
    high = len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72]
print(binary_search(numbers, 23))   # 5
print(binary_search(numbers, 10))   # -1

रिकर्सिव बाइनरी सर्च:

def binary_search_recursive(lst, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if lst[mid] == target:
        return mid
    elif lst[mid] < target:
        return binary_search_recursive(lst, target, mid + 1, high)
    else:
        return binary_search_recursive(lst, target, low, mid - 1)

बाइनरी सर्च की जटिलता:

• सर्वश्रेष्ठ स्थिति: O(1) (लक्ष्य मध्य में हो)
• सबसे खराब और औसत स्थिति: O(log n)
• स्थान जटिलता: इटरेटिव में O(1), रिकर्सिव में O(log n) (कॉल स्टैक)

4. बाइनरी सर्च का कार्य-उदाहरण

मान लीजिए सूची [2, 5, 8, 12, 16, 23, 38] है और लक्ष्य 23 है।

low=0, high=6 → mid=(0+6)//2 = 3 → lst[3]=12
12 < 23 → low=4
low=4, high=6 → mid=(4+6)//2 = 5 → lst[5]=23
23 == 23 → स्थिति 5 लौटाएँ

इस उदाहरण में केवल 2 तुलनाओं में उत्तर मिल गया, जबकि रैखिक सर्च में 6 तुलनाएँ होतीं।

5. रैखिक और बाइनरी सर्च की तुलना

बाइनरी सर्च बड़ी सूचियों पर रैखिक सर्च से काफी तेज़ होती है। उदाहरण के लिए, 1,000,000 तत्वों की सूची में रैखिक सर्च अधिकतम 1,000,000 तुलनाएँ करेगी, जबकि बाइनरी सर्च अधिकतम 20 तुलनाओं में (क्योंकि log₂(1000000) ≈ 20) उत्तर दे देगी।

6. कब कौन सी सर्च चुनें (Choosing a Search Method)

सर्च विधि का चयन निम्नलिखित परिस्थितियों पर निर्भर करता है:

1. छोटी सूची: रैखिक सर्च उपयुक्त है, क्योंकि इसका कार्यान्वयन सरल है और O(n) भी कम होता है।
2. असॉर्टेड सूची: केवल रैखिक सर्च ही कार्य करती है, क्योंकि बाइनरी सर्च को सॉर्टेड डेटा चाहिए।
3. बड़ी सॉर्टेड सूची: बाइनरी सर्च सबसे कुशल है, क्योंकि O(log n) में खोज संभव है।
4. बार-बार खोज: यदि बार-बार खोज करनी है तो सूची को पहले सॉर्ट करना और फिर बाइनरी सर्च करना अधिक कुशल होता है।

यदि सूची छोटी है तो सॉर्टिंग का अतिरिक्त खर्च उचित नहीं होता और रैखिक सर्च ही बेहतर है। लेकिन यदि सूची बड़ी है और कई खोजें करनी हैं तो एक बार सॉर्ट करके बाइनरी सर्च करना लाभदायक होता है। इस प्रकार के विश्लेषणात्मक निर्णय परीक्षा के उच्च-मूल्य वाले प्रश्नों में पूछे जाते हैं।

7. रैखिक और बाइनरी सर्च का आउटपुट विश्लेषण

कोड-आउटपुट प्रश्नों को हल करने का अभ्यास:

def linear_search(lst, target):
    for i in range(len(lst)):
        if lst[i] == target:
            return i
    return -1

def binary_search(lst, target):
    low, high = 0, len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

numbers = [10, 20, 30, 40, 50]
print(linear_search(numbers, 30))    # 2
print(binary_search(numbers, 40))    # 3
print(binary_search(numbers, 25))    # -1

इस उदाहरण में रैखिक सर्च 30 को तीसरी स्थिति (अनुक्रमांक 2) पर पाता है। बाइनरी सर्च सॉर्टेड सूची में 40 को अनुक्रमांक 3 पर पाता है, जबकि 25 अनुपस्थित होने पर -1 लौटता है। दोनों एल्गोरिथ्मों के चरणबद्ध विश्लेषण से आउटपुट सही-सही लिखा जा सकता है।

त्वरित पुनरावृत्ति तालिकाएँ

सर्च एल्गोरिथ्म का सारांश

बाइनरी सर्च के चरण

माइंड मैप

महत्वपूर्ण आरेख (SVG)

आरेख 1: बाइनरी सर्च का प्रवाह

आरेख 2: रैखिक बनाम बाइनरी सर्च

सामान्य गलतियाँ

1. बाइनरी सर्च को असॉर्टेड सूची पर उपयोग करना: यदि सूची सॉर्ट नहीं है तो बाइनरी सर्च गलत परिणाम देती है या तत्व मिलने के बाद भी -1 लौटा सकती है।
2. low <= high की शर्त को भूलना: केवल low < high उपयोग करने पर एकल तत्व वाली सूची में त्रुटि हो सकती है।
3. mid की गणना का क्रम: (low + high) // 2 सही है; गलत कोष्ठक से फ़्लोट या गलत मान आ सकता है।
4. रैखिक सर्च में break का उपयोग न करना: तत्व मिलने के बाद भी लूप जारी रखना अकुशल है।
5. -1 का अर्थ भूलना: -1 यह दर्शाता है कि तत्व नहीं मिला; इसे सही स्थिति न समझें।
6. रिकर्सिव बाइनरी सर्च में आधार स्थिति (low > high) न लिखना: अनंत रिकर्शन से स्टैक ओवरफ्लो होता है।

परीक्षा युक्तियाँ

1. दिए गए कोड में सर्च एल्गोरिथ्म पहचानें: यदि for i in range क्रमिक तुलना है तो रैखिक; यदि mid और low/high है तो बाइनरी।
2. बाइनरी सर्च के प्रत्येक चरण में low, high और mid का मान लिखने का अभ्यास करें।
3. बाइनरी सर्च के लिए "सूची सॉर्ट होनी चाहिए" को हमेशा याद रखें - यह बहुत पूछा जाता है।
4. O(n) बनाम O(log n) के अंतर को एक उदाहरण (जैसे 1,000,000 तत्व) के साथ समझाएँ।
5. रिकर्सिव और इटरेटिव दोनों रूपों में बाइनरी सर्च लिखने का अभ्यास करें।
6. दिए गए सर्च कोड का आउटपुट लिखते समय पूरी प्रक्रिया (चरण) दिखाएं, इससे क्रमबद्ध अंक मिलते हैं।

निष्कर्ष

सर्चिंग डेटा संरचना का सबसे बुनियादी और आवश्यक ऑपरेशन है। रैखिक सर्च सरल और सार्वभौमिक है परंतु बड़ी सूचियों पर धीमी है, जबकि बाइनरी सर्च केवल सॉर्टेड सूचियों पर O(log n) में अत्यधिक कुशल खोज करती है। बाइनरी सर्च "विभाजित और जीत" सिद्धांत पर मध्य तत्व की तुलना कर खोज क्षेत्र को आधा करती है। दोनों विधियों का चुनाव डेटा की प्रकृति और सूची के आकार पर निर्भर करता है। इन एल्गोरिथ्मों की चरणबद्ध समझ, जटिलता विश्लेषण और पाइथन कार्यान्वयन का अभ्यास परीक्षा में सफलता के लिए अनिवार्य है।