खोजना और क्रमबद्ध करना

रैखिक खोज

खोजने का अर्थ है, एक संग्रह और एक मान दिए होने पर, यह उत्तर देना कि मान मौजूद है या नहीं और कहाँ है। डेटा के क्रम के बारे में कोई जानकारी न हो, तो उन्हें एक-एक करके देखने के सिवा कोई रणनीति नहीं है: यही रैखिक खोज है। जब मान मौजूद नहीं होता, तो यह पाठ्यक्रम values.size() लौटाता है, वह पहली स्थिति जो वेक्टर की नहीं है: यह मान्य इंडेक्स नहीं है, इसलिए किसी उत्तर से इसका भ्रम नहीं होता, और यह वही परिपाटी है जिसका पालन लाइब्रेरी करती है, जैसा पाँचवें अनुभाग में दिखेगा।

#include <cstddef>#include <print>#include <vector>​// पूर्व-शर्त: कोई नहीं।// पश्च-शर्त: वह सबसे छोटा इंडेक्स i लौटाता है जिसके लिए values[i] == target,// या values.size(), यदि target मौजूद नहीं है।std::size_t linearSearch(const std::vector<int>& values, int target){    // निश्चर: target, values[0], ..., values[i - 1] में नहीं है।    for (std::size_t i{0}; i < values.size(); ++i) {        if (values[i] == target) {            return i;        }    }    return values.size();}​int main(){    const std::vector<int> codes{405, 112, 318, 207, 112, 530};    for (const int target : {207, 112, 999}) {        const std::size_t pos{linearSearch(codes, target)};        if (pos == codes.size()) {            std::println("{}: मौजूद नहीं", target);        } else {            std::println("{}: स्थिति {}", target, pos);        }    }}

207: स्थिति 3112: स्थिति 1999: मौजूद नहीं

पंक्ति 10 का निश्चर शुद्धता देता है। आरंभ में, जब i शून्य के बराबर है, वह एक खाली हिस्से के बारे में कुछ कहता है और सत्य है। यदि वह किसी चक्कर के आरंभ में सत्य है और values[i] खोजा गया मान नहीं है, तो वह चक्कर के अंत में एक अवयव अधिक के साथ सत्य रहता है। किंतु लूप के दो निकास हैं: यदि return i; निष्पादित होता है, तो values[i] खोजा गया मान है और, निश्चर के अनुसार, उससे पहले का कोई अवयव वह मान नहीं था, अतः i पहली उपस्थिति है (इसीलिए 112, जो दो बार आता है, स्थिति 1 पर बताया जाता है); यदि लूप शर्त के कारण समाप्त होता है, तो i का मान values.size() होता है, और निश्चर कहता है कि मान कहीं नहीं है। लूप के भीतर का return फ़ंक्शन को, और उसके साथ लूप को, समाप्त कर देता है, और एक फ़्लैग की ज़रूरत नहीं रहती।

लागत, पाठ एल्गोरिदम की लागत के अर्थ में, तुलनाओं values[i] == target से मापी जाती है। यदि मान मौजूद नहीं है, तो ठीक $n$ तुलनाएँ होती हैं, हर अवयव के लिए एक: यह सबसे बुरी स्थिति है। यदि वह स्थिति $p$ पर है, तो $p + 1$ तुलनाएँ होती हैं। अतः रैखिक खोज $O(n)$ है: दुगुना डेटा, दुगुना काम। अतिरिक्त जानकारी के बिना इससे बेहतर नहीं किया जा सकता: जो एल्गोरिदम किसी अवयव को देखना छोड़ दे, वह नहीं जान सकता कि मान वहीं था या नहीं।