द्विआधारी खोज एक सरणी में एक तत्व खोजने का सबसे आसान तरीका है

अक्सर, प्रोग्रामर, यहां तक कि शुरुआती, इस तथ्य से सामना कर रहे हैं कि संख्या का एक सेट है जिसमें एक निश्चित संख्या मिलनी आवश्यक है। इस संग्रह को एक सरणी कहा जाता है। और इसमें सही तत्व ढूंढने के लिए, बहुत सारे तरीके हैं लेकिन उनमें से सबसे आसान द्विआधारी खोज है विधि क्या है? और एक द्विआधारी खोज कैसे कार्यान्वित करें? पास्कल ऐसे कार्यक्रम के आयोजन के लिए सरलतम वातावरण है, इसलिए हम इसे अध्ययन के लिए उपयोग करेंगे।

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

तो, इस पद्धति का सिद्धांत क्या है? तत्काल यह कहने में सार्थक है कि द्विआधारी खोज किसी भी सरणी में काम नहीं करती है, लेकिन केवल संख्याओं के सेट में प्रत्येक अगले चरण में, सरणी का औसत तत्व लिया जाता है (तत्व संख्या का संदर्भ दे रहा है)। यदि वांछित संख्या औसत से अधिक है , तो बायीं तरफ, जो औसत तत्व से कम है, इसे हटा दिया जा सकता है और वहां खोज नहीं की जा सकती। इसके विपरीत, अगर औसत से कम, दाईं ओर की संख्याओं में से, आप उनके लिए नहीं देख सकते हैं। इसके बाद, हम एक नया खोज क्षेत्र चुनेंगे, जहां पहला तत्व पूरे सरणी का मध्य तत्व होगा, और आखिरी एक आखिरी होगा नए क्षेत्र की औसत संख्या पूरे खंड का ¼ होगी, वह (अंतिम तत्व + संपूर्ण सरणी का औसत तत्व) / 2 है। दोबारा, एक ही संचालन किया जाता है - सरणी की औसत संख्या के साथ तुलना। यदि वांछित मूल्य औसत से कम है, दाहिनी ओर त्याग दें, और जब तक यह मध्य तत्व नहीं मिल जाता है तब तक ऐसा करें।

बेशक, उदाहरण को देखने का सबसे अच्छा तरीका है कि कैसे एक द्विआधारी खोज लिखना है पास्कल यहाँ किसी के लिए उपयुक्त है - संस्करण महत्वपूर्ण नहीं है चलो एक साधारण प्रोग्राम लिखते हैं।

इसमें 1 से h नाम की एक सरणी "massiv" होगी, एक निचले खोज सीमा, जो "निज़" नामक एक वेरियंट है, जिसका ऊपरी बंड नाम "वर्ह" है, मध्य खोज तत्व "sredn" है; और आवश्यक संख्या "आईएसके" है

इसलिए, पहले खोज अंतराल की ऊपरी और निचली सीमाएं असाइन करें:

निज: = 1;
वेरह: = एच + 1;

तब हम चक्र को व्यवस्थित करते हैं "जबकि नीचे ऊपरी सीमा से कम है":

जबकि निज <वर् - 1 करो
शुरू करना

प्रत्येक चरण में, खंड 2 से विभाजित करें:

Sredn: = (निज़ + वर्ह) div 2; {Div फ़ंक्शन का उपयोग करें क्योंकि हम शेष बांटते हैं}

हर बार जब हम एक जांच करते हैं यदि औसत वांछित के बराबर है, तो हम चक्र को बाधित करते हैं, क्योंकि वांछित तत्व पहले से ही पाया गया है:

Іf sredn = isk तो तोड़;

अगर सरणी का मध्यम तत्व हम से ढूंढने वाला है, तो हम बाईं तरफ त्याग देते हैं, अर्थात हम ऊपरी सीमा तक मध्य तत्व देते हैं:

यदि मासत्व [sredn]> आइस्क तो verh: = sredn;

और यदि इसके विपरीत, तो हम इसे कम सीमा बनाते हैं:

अन्य निज: = सरडेन;
अंत;

यह सब यही कार्यक्रम में होगा।

चलो विश्लेषण करते हैं कि बाइनरी पद्धति कैसे अभ्यास में दिखाई देगी। इस तरह की एक सरणी लें: 1, 3, 5, 7, 10, 12, 18 और उसमें नंबर 12 की तलाश करें।

कुल में, हमारे पास 7 तत्व हैं, इसलिए औसत चौथे होगा, इसका मान 7 होगा।

चूंकि 12 7 से अधिक है, इसलिए तत्वों 1,3 और 5 को हटाया जा सकता है। इसके बाद, हमारे पास 4 नंबर शेष हैं, 4/2 बिना शेष 2 है। तो, नया मध्य तत्व 10 होगा।

चूंकि 12 10 से अधिक है, हम 7 को छोड़ देते हैं। केवल 10, 12 और 18 बचे हैं

यहां मध्यम तत्व पहले से ही 12 है, यह आवश्यक संख्या है कार्य पूरा हो गया है - संख्या 12 पाया जाता है।