रैखिक और द्विआधारी खोज

ऐरे के सक्रिय भाग में खोज

खोज का प्रश्न है: क्या दिया गया key संग्रह में है? इस पाठ में हम उसकी पहली स्थिति का index लौटाएँगे। पिछले वृद्धि-विश्लेषण पाठ से मुख्य बात याद रखें: लागत की तुलना से पहले पूर्वशर्त, परिणाम का अर्थ और गिना जाने वाला कार्य स्पष्ट होना चाहिए। पूर्वज्ञान: ऐरे के तत्व और वैध index, array parameters, लूप, फ़ंक्शन तथा algorithm-growth-and-asymptotic-bounds। यह खोज का परिचय है, सभी algorithms का पूरा पाठ्यक्रम नहीं।

सक्रिय डेटा a[0] से a[n-1] तक है, जहाँ 0 <= n <= CAP और CAP = 8 है। कॉलर कम से कम CAP तत्वों वाला जीवित, initialized int ऐरे देता है; n बताता है कि कितने तत्व उपयोग में हैं। निष्क्रिय स्थान का शून्य खोजे जाने वाले डेटा में शामिल नहीं है। n = 0 उसी मौजूद ऐरे का खाली prefix है, शून्य लंबाई का C ऐरे नहीं। प्रोग्राम में allocation या user input नहीं है।

दोनों फ़ंक्शन SearchResult रिकॉर्ड लौटाते हैं। index सफल खोज में सबसे छोटा matching zero-based index, वैध खोज में key न मिलने पर -1, और अस्वीकृत pointer/length पर -2 है। comparisons केवल वास्तव में evaluate हुए element-versus-key expressions गिनता है: a[i] == key, a[mid] < key और अंतिम a[lo] == key। लूप की शर्त, index गणना, n की जाँच और दो indices की तुलना इसमें नहीं गिनी जाती। यह परिभाषित लागत मॉडल है, वास्तविक समय का मापन नहीं।

रैखिक खोज: मान किसी भी क्रम में हों

Linear search indices 0,1,... पर जाँच करके पहली equality पर लौटती है। sorted क्रम आवश्यक नहीं है। index i की जाँच से पहले उससे छोटे सभी indices देखे जा चुके हैं और वहाँ key नहीं मिला। इसलिए i लौटाने पर पहली occurrence मिलती है; पूरा prefix समाप्त होने पर अनुपस्थिति सिद्ध होती है। विफल equality के बाद i बढ़ता है और हर read से पहले 0 <= i < n रहता है।

उदाहरण के लिए बाईं ओर से चाबी के डिब्बे खोलकर पहली मिलती चाबी ढूँढें। खाली पंक्ति में कोई डिब्बा नहीं खोलना। यह उपमा खोज का क्रम समझाती है; डिब्बा हिलाने या खोलने का भौतिक समय हमारे C comparison model में शामिल नहीं है।

n >= 1 पर पहली occurrence index p हो तो ठीक p+1 equalities होती हैं। key अनुपस्थित हो तो n। सभी अनुमत arrays और keys में best-case count 1 और worst-case count n है: best Θ(1), worst Θ(n)। n = 0 पर count 0 है। probability model दिए बिना average-case का एक निश्चित सूत्र नहीं बताया जा सकता।

द्विआधारी खोज: क्रम की पूर्वशर्त का उपयोग

यह binary search सक्रिय prefix को आरोही, nondecreasing क्रम में माँगती है: a[i] <= a[i+1]। बराबर मान हो सकते हैं। फ़ंक्शन केवल non-NULL pointer और 0 <= n <= CAP जाँचता है; वह sortedness जाँचने के लिए scan नहीं करता। सही storage और initialized मानों की तरह sortedness भी कॉलर की जिम्मेदारी है। unsorted prefix देने पर यह contract टूटता है और गलत परिणाम मिल सकता है; आवश्यक नहीं कि -2 लौटे। उसी unsorted prefix पर linear search सही रहती है।

हम lower bound ढूँढते हैं: पहला स्थान जिसका मान key से कम नहीं है, या ऐसा स्थान न होने पर n। unresolved interval [lo,hi) है: lo शामिल, hi शामिल नहीं। शुरू में lo = 0, hi = n। जब तक lo < hi, mid = lo + (hi-lo)/2 लें:

• a[mid] < key हो तो sortedness के कारण mid तक सभी मान key से छोटे हैं। lo = mid+1 करें।
• अन्यथा a[mid] >= key है। mid पहला उपयुक्त स्थान हो सकता है, या उससे पहले कोई स्थान हो सकता है। hi = mid करें। mid unresolved interval से बाहर जाता है, लेकिन संभावित सीमा बना रहता है।

Equality मिलते ही न लौटें: उससे कोई occurrence मिलेगी, पहली मिलना निश्चित नहीं होगा। इस half-open पद्धति में hi = mid-1 भी न करें; वह अलग invariant वाली पद्धति का update है।

समाप्ति पर lo = hi एक boundary है, अपने-आप match नहीं। पहले lo < n जाँचें, तभी a[lo] == key देखें। lo == n होने पर a[lo] सक्रिय prefix के बाहर है, और n == CAP पर actual ऐरे के भी बाहर है। lo < n लेकिन a[lo] > key होने पर भी key अनुपस्थित है। दोनों अनुपस्थित मामलों में -1 लौटता है।

पूरा bounded C11 प्रोग्राम

#include <limits.h>
#include <stdio.h>

enum { CAP = 8 };
typedef struct {
    int index;       /* -2 invalid input; -1 absent; otherwise first index */
    int comparisons; /* only element-versus-key comparisons */
} SearchResult;

SearchResult linear_first(const int a[CAP], int n, int key) {
    SearchResult r = {-2, 0};
    if (a == NULL || n < 0 || n > CAP) {
        return r;
    }
    r.index = -1;
    for (int i = 0; i < n; ++i) {
        ++r.comparisons;
        if (a[i] == key) {
            r.index = i;
            return r;
        }
    }
    return r;
}

/* Caller promises a[0..n) is sorted in nondecreasing order. */
SearchResult binary_first(const int a[CAP], int n, int key) {
    SearchResult r = {-2, 0};
    if (a == NULL || n < 0 || n > CAP) {
        return r;
    }
    int lo = 0;
    int hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        ++r.comparisons;
        if (a[mid] < key) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    r.index = -1;
    if (lo < n) {
        ++r.comparisons;
        if (a[lo] == key) {
            r.index = lo;
        }
    }
    return r;
}

int main(void) {
    const int a[CAP] = {-4, 1, 1, 1, 7, 12, 0, 0};
    const int keys[3] = {1, 6, 20};
    for (int k = 0; k < 3; ++k) {
        SearchResult l = linear_first(a, 6, keys[k]);
        SearchResult b = binary_first(a, 6, keys[k]);
        printf("key=%d linear=(%d,%d) binary=(%d,%d)\n",
               keys[k], l.index, l.comparisons, b.index, b.comparisons);
    }
    return 0;
}

ठीक output:

key=1 linear=(1,2) binary=(1,4)
key=6 linear=(-1,6) binary=(-1,4)
key=20 linear=(-1,6) binary=(-1,2)

हर जोड़ा (index, comparisons) है। छह सक्रिय मान [-4,1,1,1,7,12] हैं; अंत के दो allocated zero slots निष्क्रिय हैं। INT_MIN और INT_MAX भी वैध मान और key हैं: फ़ंक्शन सीधे तुलना करते हैं, घटाकर तुलना नहीं करते। चरम signed integers का subtraction overflow कर सकता है; सीधी तुलना में यह समस्या नहीं है। साथ दिए author tests में limits.h से ये constants मिलते हैं।

C contract को ध्यान से पढ़ें

typedef struct दो int fields वाले रिकॉर्ड को नाम देता है। {-2,0} declaration के क्रम में fields initialize करता है। r.index एक field चुनता है। रिकॉर्ड लौटाने पर उसके दोनों मान कॉलर को copy होते हैं। फ़ंक्शन parameter const int a[CAP] को C, const int के pointer में adjust करता है: यह notation आठ तत्वों की capacity enforce नहीं करता, न capacity साथ पहुँचाता है। सही आकार का वास्तविक storage देना कॉलर की जिम्मेदारी है। ऐरे में बदलाव नहीं होता।

इस सरल contract में n शून्य होने पर भी NULL अस्वीकृत है। short-circuit || वाली शर्त किसी array read से पहले NULL या गलत n अस्वीकार करती है। वह dangling pointer, छोटा object, uninitialized तत्व या concurrent mutation नहीं पहचान सकती। हर स्वीकार्य non-NULL argument वादे के अनुसार जीवित initialized ऐरे का पता हो; calls sequential हैं। उदाहरण में वास्तव में CAP तत्व allocated हैं।

++i में i एक बढ़ता है; == equality, < strict order और = assignment है। main का for लूप तीन keys चुनता है; %d int छापता है और \n नई पंक्ति शुरू करता है। lo, hi, mid तथा n की सीमाएँ 0 से 8 हैं। linear count अधिकतम 8 और binary count अधिकतम 5 है; सभी दिखाई गणनाएँ int में सुरक्षित हैं। midpoint का रूप सामान्य lo+hi overflow के खतरे से बचाता है, क्योंकि 0 <= lo <= hi <= n होने से hi-lo representable है।

Binary search सही क्यों है और रुकती क्यों है?

हर iteration के शुरू में invariant है:

1. 0 <= lo <= hi <= n।
2. lo से पहले हर सक्रिय मान < key है।
3. hi से शुरू होने वाला हर सक्रिय मान >= key है।

शुरुआती [0,n) के बाहर कोई सक्रिय स्थान नहीं, इसलिए दोनों value शर्तें शुरू में अपने-आप सही हैं। lo < hi पर integer division से lo <= mid < hi <= n मिलता है; इसलिए a[mid] वैध read है। a[mid] < key होने पर sortedness, mid तक दूसरी शर्त सिद्ध करती है; lo = mid+1 तीनों शर्तें बचाता है। अन्यथा sortedness, mid से तीसरी शर्त सिद्ध करती है; hi = mid भी तीनों शर्तें बचाता है। हर update में nonnegative integer hi-lo सख्ती से घटता है, इसलिए loop रुकता है।

lo = hi पर सभी पहले के मान key से छोटे और सभी बाद के सक्रिय मान key से कम नहीं हैं। यही lower-bound boundary है। वहाँ सीमा जाँचने के बाद equality मिलने पर पहली occurrence सिद्ध है। बड़ा मान या boundary n मिले तो key अनुपस्थित है। n = 0 पर शुरू में lo = hi = 0 है; loop नहीं चलता, lo < n असत्य है, और कोई तत्व पढ़े बिना (-1,0) लौटता है।

हल किया trace 1: duplicates में मौजूद key

प्रोग्राम का सक्रिय [-4,1,1,1,7,12], n = 6 और key = 1 लें। Linear पहले index 0 पर -4 == 1 की असत्य और फिर index 1 पर सत्य तुलना करती है: पहला index 1, कुल दो key comparisons।

अब lo = hi = 1। चूँकि 1 < 6, अंतिम 1 == 1 जाँच सफल है। Binary में तीन loop comparisons और एक equality, कुल चार comparisons हैं। पहली देखी equality index 3 पर तुरंत लौटने से first-occurrence contract टूटता। इस छोटे उदाहरण में binary, linear से अधिक comparisons करती है; हर query पर कम comparisons का दावा सही नहीं है।

हल किया trace 2: दो मानों के बीच अनुपस्थित key

उसी ऐरे में key = 6 लें। [0,6) में mid 3, 1 < 6 सत्य, इसलिए lo = 4। [4,6) में mid 5, 12 < 6 असत्य, इसलिए hi = 5। [4,5) में mid 4, 7 < 6 असत्य, इसलिए hi = 4। सीमा 4 मिली। 4 < 6 होने से मान 7 पढ़ सकते हैं; 7 == 6 असत्य है। परिणाम -1, तीन loop comparisons और एक equality = चार। Linear सभी छह equalities असफल होने पर -1 देती है। Lower-bound position मिलना membership का प्रमाण नहीं।

हल किया trace 3: अधिकतम से बड़ा अनुपस्थित key

उसी ऐरे में key = 20 लें। [0,6) में mid 3, 1 < 20 सत्य, lo = 4। [4,6) में mid 5, 12 < 20 सत्य, lo = 6। अब interval [6,6) खाली है। lo < n असत्य होने से अंतिम element equality होती ही नहीं। Binary ठीक दो key comparisons पर -1, linear छह पर -1 देती है। अतिरिक्त allocated zeros खोज में शामिल नहीं होते।

लागत की ईमानदार तुलना

इस algorithm के scalable रूप में लंबाई m > 0 वाला interval अधिकतम floor(m/2) तक घटता है। n >= 1 पर loop अधिकतम floor(log2 n)+1 बार चलता है। अंतिम membership जाँच अधिकतम एक element-key comparison जोड़ती है; इसलिए कुल upper bound floor(log2 n)+2 है। हर query पर ठीक इतनी comparisons होने का दावा नहीं है: तीन traces में 4,4,2 मिलीं।

यह lower-bound रूप equality मिलने पर भी interval छोटा करता रहता है। n >= 1 के inputs में best और worst counts दोनों Θ(log(n+1)) की तरह बढ़ते हैं; n >= 2 के लिए Θ(log n) लिख सकते हैं। किसी भी matching midpoint पर तुरंत लौटने वाले अलग binary-search algorithm का best Θ(1) होता है; उसे इस code पर लागू न करें। n = 0 में शून्य comparisons हैं। कोई average-case दावा नहीं किया गया है। scalable-array मॉडल में दोनों functions का auxiliary space Θ(1) है; कॉलर का array storage अलग है।

CAP = 8 से इस executable का domain सीमित है। Asymptotic कथन पर्याप्त वैध storage और representable indices वाले algorithms के बढ़ते input परिवार के बारे में हैं, इस exact function में असीमित n देने के बारे में नहीं। यहाँ निश्चित setup और length checks constant cost हैं।

हर binary query से पहले पूरे prefix की sortedness जाँच जोड़ें तो n >= 1 पर n-1 adjacent pairs जाँचने में Θ(n) काम लगेगा। संयुक्त per-query worst-case समय Θ(n) होगा, Θ(log n) नहीं। unordered डेटा को पहले sort करने की भी अलग लागत है और मूल indices बदल सकते हैं। इन लागतों को न छिपाएँ। अपरिवर्तित already-sorted array पर कई searches हों तो existing क्रम का लाभ मिलता है; एक बार order validate करें तो उस एकमुश्त काम को अलग गिनें। इस पाठ में sorting या sortedness-validation algorithm implement नहीं किया गया है।

मुख्य बातें

• Linear को value order की जरूरत नहीं; दोनों functions पहली matching zero-based position लौटाते हैं।
• Binary का सक्रिय prefix nondecreasing होना चाहिए; pointer/length checks यह promise नहीं जाँचतीं।
• [lo,hi) में hi = n वैध boundary है; चलते loop में midpoint, hi से छोटा है।
• Binary loop में equality पर hi बाईं ओर जाता है; guarded अंतिम equality membership बताती है।
• Exact code की expressions गिनें; अंतिम equality केवल चलने पर गिनें।
• सीधी तुलना INT_MIN/INT_MAX को subtraction overflow के बिना संभालती है।
• Lower-bound और early-return binary के best-case व्यवहार अलग हैं।

दो अतिरिक्त अभ्यास

1. उन्हीं छह मानों में key = -5 का trace करें। उत्तर: linear छह असफल comparisons करती है। Binary midpoints 3,1,0 पर तीनों < -5 tests असत्य हैं। Boundary 0 वैध है, लेकिन -4 == -5 असत्य है; binary (-1,4) लौटाती है।
2. CAP slots वाले जीवित int ऐरे का सक्रिय prefix [2,2,2,2] हो और key 2 हो। उत्तर: linear (0,1) देती है। Binary midpoints 2,1,0 पर हर बार hi घटाती है, फिर a[0] == 2 जाँचकर (0,4) देती है। midpoint 2 पर तुरंत लौटना पहली occurrence देने की शर्त क्यों तोड़ेगा, समझाएँ।

छह मौलिक, एक-सही-उत्तर वाले अभ्यास प्रश्न

चार में से ठीक एक विकल्प चुनें। ये मौलिक अभ्यास प्रश्न हैं।

1

सक्रिय [9,2,9,1] और key 9 पर linear_first क्या (index, comparisons) लौटाती है?

A. (0,1) B. (2,3) C. (-2,0) D. (0,4)

उत्तर: A

A सही है: index 0 पर 9 है; पहली तुलना पर तुरंत return होता है।

B गलत है: index 2 बाद की occurrence है; function 0 पर लौट चुकी है।

C गलत है: वैध pointer और length पर linear search unsorted prefix को अस्वीकार नहीं करती।

D गलत है: जल्दी return होने से बाकी तीन comparisons नहीं होतीं।

2

[-4,1,1,1,7,12], n=6 और key=1 पर दिखाई binary_first क्या लौटाती है?

A. (3,1) B. (1,3) C. (1,4) D. (-1,4)

उत्तर: C

A गलत है: midpoint 3 पर equality से hi घटता है, वहाँ return नहीं होता।

B गलत है: तीन loop comparisons में अंतिम membership equality छूट गई।

C सही है: midpoints 3,1,0 से boundary 1 मिलती है; अंतिम equality चौथी comparison है।

D गलत है: boundary 1 पर key 1 मौजूद है, इसलिए membership सफल है।

3

वैध call में binary_first के अंत में lo=n हो, तो आगे क्या होना चाहिए?

A. अनुपस्थिति की पुष्टि के लिए a[n] पढ़ें। B. Element equality किए बिना -1 लौटाएँ। C. n को matching index लौटाएँ। D. hi=n-1 से दोबारा शुरू करें।

उत्तर: B

A गलत है: index n सक्रिय prefix से बाहर है और full capacity पर storage से भी बाहर है।

B सही है: lo<n असत्य है; सभी सक्रिय मान key से छोटे हैं, इसलिए match नहीं है।

C गलत है: matching indices 0 से n-1 तक हैं; n केवल boundary है।

D गलत है: invariant अनुपस्थिति सिद्ध कर चुका है, फिर शुरू करना जरूरी नहीं।

4

कौन-सी पूर्वशर्त binary_first के लिए जरूरी है, linear_first के लिए नहीं?

A. हर मान positive हो। B. सभी मान अलग हों। C. key पहले से मौजूद हो। D. सक्रिय prefix nondecreasing हो।

उत्तर: D

A गलत है: दोनों algorithms negative मान तथा INT_MIN स्वीकारते हैं।

B गलत है: duplicates अनुमत हैं; दोनों पहली occurrence देती हैं।

C गलत है: दोनों absent key संभालती हैं।

D सही है: sorted क्रम से ही midpoint तुलना के बाद पूरा एक भाग हटाना उचित है।

5

CAP तत्वों वाले जीवित ऐरे में n=0 हो तो दोनों दिखाई functions क्या लौटाती हैं?

A. (-1,0) B. (-2,0) C. (0,1) D. (-1,1)

उत्तर: A

A सही है: वैध खाली prefix में match नहीं और element-key comparisons शून्य हैं।

B गलत है: वादे के अनुसार जीवित ऐरे में शून्य length वैध है; NULL देने पर error होता।

C गलत है: खाली prefix में matching के लिए index 0 का कोई सक्रिय तत्व नहीं है।

D गलत है: न loop और न guarded अंतिम equality कोई तत्व पढ़ती है।

6

Scalable रूप में हर binary query से पहले पूरे prefix की sortedness scan हो। n>=2 पर संयुक्त per-query worst-case समय क्या है?

A. Θ(1) B. Θ(log n) C. Θ(n) D. Θ(n²)

उत्तर: C

A गलत है: scan n-1 adjacent pairs देखती है, इसलिए बढ़ते n में constant नहीं है।

B गलत है: इसमें binary phase गिना गया है लेकिन पूरा validation scan छूट गया है।

C सही है: Θ(n) validation और O(log n) search जोड़ने पर कुल Θ(n) है; ये क्रमिक phases हैं, nested नहीं।

D गलत है: linear और logarithmic phases जोड़ने से quadratic nested scan नहीं बनता।