बायनरी शोध - सर्वात सोपा मार्ग एका एॅरेमधील घटक शोधण्यासाठी

बरेचदा, प्रोग्रामर, अगदी सुरुवातीला, क्रमांक एक संच, एक विशिष्ट क्रमांक शोधण्यासाठी आवश्यक आहे तेथे आहे की तोंड द्यावे लागले. या संग्रह अॅरे म्हणतात. आणि त्यात आयटम शोधण्यासाठी, तेथे मार्ग एक अपरिमित आहेत. पण त्यांना सर्वात सोपे उजवीकडे एक बायनरी शोध मानले जाऊ शकते. काय ही पद्धत आहे? आणि कसे बायनरी शोध अंमलबजावणी करण्यासाठी? पास्कल अशा कार्यक्रमाचे आयोजन सर्वात सोपा वातावरण आहे, त्यामुळे आम्ही अभ्यास तो वापरणार.

प्रथम, विश्लेषण, ही पद्धत फायदे काय आहेत, असे आम्ही समजू शकतो, विषय अभ्यास मध्ये काय आहे. त्यामुळे, काही शोधण्यासाठी आवश्यक जो किमान 100000000 घटक, एक आकारमान एक अॅरे द्या. अर्थात, ही समस्या सहज एक साधी रेषेचा शोध, आम्ही सायकल वापरत असलेल्या अरे आहेत ते सर्व आवश्यक घटक तुलना निराकरण होऊ शकते. समस्या ही कल्पना अंमलबजावणी खूप वेळ लागेल असे आहे. अनेक उपचार, आणि मुख्य मजकूर तीन ओळी मध्ये एक साधी पास्कल कार्यक्रमात, आपण ते लक्षात नाही, पण आम्ही शाखा आणि चांगले कार्यक्षमता मोठ्या प्रमाणात अधिक किंवा कमी मोठे प्रकल्प आले तेव्हा, कार्यक्रम खूप लोड करण्यासाठी तयार होईल. विशेषत: संगणक कमकुवत कामगिरी आहे तर. म्हणून, एक बायनरी शोध किमान दोनदा शोध वेळ कमी करते आहे.

त्यामुळे, या पद्धतीचा काम तत्त्व काय आहे? लगेच तो बायनरी शोध कोणत्याही अरे नाही आहे, पण केवळ आकडे एका क्रमवारी लावलेल्या संच कार्य करते की कोणीही म्हणू नये. अरे प्रत्येक पाऊल उचलले मध्यम घटक वेळी (घटक संख्या अर्थ). आवश्यक असल्यास संख्या जास्त आहे सरासरी, नंतर सर्व बाकी आहे, की सरासरी सेल पेक्षा कमी आहे, टाकून जाऊ शकते आणि तेथे दिसत नाही. उलट, सरासरी पेक्षा कमी असेल तर - योग्य त्या क्रमांक आपापसांत, आपण शोधू शकत नाही. मग एक नवीन शोध क्षेत्र, पहिल्या घटक संपूर्ण अरे मध्यभागी घटक, आणि गेल्या आणि गेल्या इच्छा असेल जेथे निवडा. नवीन क्षेत्र सरासरी संख्या आहे की सर्व विभाग, (अंतिम घटक + संपूर्ण अरे मध्यभागी घटक) / 2 च्या ¼ असेल. पुन्हा, त्याच ऑपरेशन आहे - अरे सरासरी संख्या एक तुलना. लक्ष्य मूल्य सरासरी पेक्षा कमी असेल, तर आपण उजव्या बाजूला नकार, आणि आता हे मध्यम घटक इच्छित नाही तोपर्यंत, पुढे काय करायचे.

अर्थात, बायनरी शोध कसे लिहायचे ते एक उदाहरण पाहू सर्वोत्तम आहे. येथे पास्कल कोणालाही भागविण्यासाठी होईल - आवृत्ती महत्वाचे नाही. एक साधा कार्यक्रम लिहा द्या.

हे नाव "massiv" अंतर्गत 1 अॅरे ह आहे, शोध खालच्या सीमा दर्शविणारा एक वेरियेबल, "niz" म्हणतात, वरील मर्यादा, "verh", सरासरी शोध संज्ञा म्हणतात - "sredn"; आणि आवश्यक संख्या - "ISK".

त्यामुळे प्रथम आम्ही श्रेणी शोध वरच्या आणि खालच्या मर्यादा लागू:

niz: = 1;
verh: = ह + 1;

मग सायकल आयोजित "पर्यंत तळाशी वरील मर्यादा पेक्षा कमी आहे":

niz सुरू

प्रत्येक पाऊल, आम्ही विभाग 2 दोन भाग होतील

sredn: = (niz + verh) div 2; {, Div कार्य वापरा उर्वरित न दुफळी कारण}

प्रत्येक वेळी पुनरावलोकन. मध्यम इच्छित असल्यास आयटम आधीच आढळले आहे कारण, सायकल व्यत्यय:

іf sredn = ISK नंतर खंडित;

इच्छित पेक्षा अधिक अरे मध्यभागी घटक, टाकून, तर डाव्या बाजूला आहे, की सरासरी वरच्या सीमा घटक नियुक्ती:

तर massiv [sredn]> ISK नंतर verh: = sredn;

आणि त्याउलट, तर तो कमी सीमा करते:

आणखी niz: = 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 आढळले.