>> [संगीत बजाना]
>> डौग लॉयड: ठीक है।
तो द्विआधारी खोज एक है हम उपयोग कर सकते हैं एल्गोरिथ्म
एक सरणी के अंदर एक तत्व खोजने के लिए।
रैखिक खोज के विपरीत, यह आवश्यकता है एक विशेष हालत पहले से मुलाकात हो
लेकिन यह इतना अधिक कुशल यदि है हालत यह है कि, वास्तव में, से मुलाकात की।
>> तो विचार यहाँ क्या हो रहा है?
यह फूट डालो और राज है।
हम के आकार को कम करना चाहते हैं आधा हर बार से खोज क्षेत्र
लक्ष्य नंबर खोजने के लिए।
यह है कि जहां हालत है हालांकि, खेलने में आता है।
हम केवल की शक्ति का लाभ उठाने कर सकते हैं तत्वों के नष्ट आधा
भी देख के बिना उन्हें सरणी हल है यदि।
>> यह एक पूर्ण मिश्रण है, हम सिर्फ हाथ से बाहर नहीं कर सकते
क्योंकि, तत्वों के आधे त्यागने हम discarding रहे हैं पता नहीं है।
लेकिन सरणी, हल किया जाता है तो हम ऐसा कर सकते हैं क्योंकि हम
करने के लिए है कि सब कुछ जानते हैं हम वर्तमान में कर रहे हैं, जहां से छोड़ा
से कम होना चाहिए मूल्य हम वर्तमान में कर रहे हैं।
और सब कुछ करने के लिए हम कर रहे हैं, जहां का अधिकार
मूल्य से अधिक होना चाहिए वर्तमान में हम देख रहे हैं।
>> तो स्यूडोकोड क्या है द्विआधारी खोज के लिए कदम?
हम जब तक इस प्रक्रिया को दोहराने सरणी या, हम के माध्यम से आगे बढ़ना के रूप में,
उप सरणियों, के छोटे टुकड़े मूल सरणी, आकार 0 से है।
मध्यबिंदु की गणना वर्तमान उप सरणी की।
>> आप के लिए देख रहे हैं मान है, तो सरणी के उस तत्व में, बंद करो।
आपने इसे पा लिया।
यह बहुत अच्छा है।
अन्यथा, लक्ष्य है, तो बीच में क्या कम से कम
इसलिए महत्व देते हैं हम देख रहे हैं के लिए, जो हम देखते हैं की तुलना में कम है
फिर इस प्रक्रिया को दोहराने, लेकिन इसके बजाय, अंत बिंदु को बदल
मूल होने का पूरी सरणी पूरा,
सिर्फ बाईं ओर होना करने के लिए जहां से हम सिर्फ देखा।
>> हम बीच बहुत अधिक थी कि पता था या लक्ष्य, मध्य से कम नहीं था
और इसलिए यह मौजूद होना चाहिए अगर यह सब पर है, सरणी में मौजूद है
कहीं मध्यबिंदु के बाईं ओर।
और इसलिए हम सरणी स्थापित करेंगे सिर्फ बाईं ओर स्थान
नई अंत बिंदु के रूप में मध्य के।
इसके विपरीत, लक्ष्य है, तो बीच में क्या से अधिक से अधिक,
हम उसी करना प्रक्रिया है, लेकिन इसके बजाय हम
होना करने के लिए प्रारंभ बिंदु बदल सिर्फ मध्यबिंदु के अधिकार के लिए
हम सिर्फ गणना की थी।
और फिर, हम प्रक्रिया को फिर से शुरू करते हैं।
>> ठीक है, यह कल्पना करते हैं?
तो जा रहा है और यहां पर एक बहुत कुछ है, लेकिन यहाँ 15 तत्वों की एक सरणी है।
और हम ट्रैक रखने के होने जा रहे हैं एक बहुत अधिक सामान इस समय की।
तो रैखिक खोज में, हम थे बस एक लक्ष्य के बारे में देखभाल।
लेकिन इस बार हम करना चाहते हैं हम कर रहे हैं, जहां के बारे में परवाह
देखने के लिए शुरू, जहां हम देख रोक रहे हैं,
और मध्य क्या है वर्तमान सरणी की।
यहाँ तो हम द्विआधारी खोज के साथ चलते हैं।
हम बहुत ज्यादा अच्छा जाना, सही कह रहे हो?
मैं सिर्फ नीचे डाल करने के लिए जा रहा हूँ सूचकांक का एक सेट यहाँ नीचे।
यह मूल रूप से बस क्या तत्व है सरणी के बारे में हम बात कर रहे हैं।
रैखिक खोज के साथ, हम हम यद्यपि के रूप में, परवाह
कितने पता करने की जरूरत हम पर iterating रहे तत्वों,
लेकिन हम वास्तव में परवाह नहीं है क्या तत्व हम वर्तमान में देख रहे हैं।
द्विआधारी खोज में, हम करते हैं।
और इसलिए उन बस रहे हैं वहाँ एक छोटे से गाइड के रूप में।
>> इसलिए हम सही, शुरू कर सकते हैं?
खैर, काफी नहीं है।
मैंने क्या कहा याद रखें द्विआधारी खोज के बारे में?
हम एक पर यह नहीं कर सकता बाकी अवर्गीकृत सरणी या,
हम गारंटी है कि नहीं कर रहे हैं कुछ तत्वों या मान नहीं रहे
गलती से किया जा रहा है त्याग जब हम बस
सरणी में से आधे की अनदेखी करने का फैसला।
>> तो द्विआधारी खोज के साथ एक कदम आप एक क्रमबद्ध सरणी होना आवश्यक है।
और अगर आप छँटाई के किसी भी उपयोग कर सकते हैं हम के बारे में बात की है एल्गोरिदम
स्थिति यह है कि आप प्राप्त करने के लिए।
तो अब, हम एक स्थिति जहां में हैं हम द्विआधारी खोज प्रदर्शन कर सकते हैं।
>> तो चलो इस प्रक्रिया को दोहराने दें कदम से कदम और रख
हम जाने के रूप में क्या हो रहा है का ट्रैक।
तो पहले हम की गणना करने की ज़रूरत है वर्तमान सरणी का मध्यबिंदु।
खैर, हम सबसे पहले, हम कर रहे हैं कहूँगा सब के मूल्य 19 के लिए देख रहे हैं।
हम संख्या 19 खोजने की कोशिश कर रहे हैं।
इस के पहले तत्व सरणी, सूचकांक शून्य पर स्थित है
और इस के अंतिम तत्व सरणी सूचकांक 14 पर स्थित है।
और इसलिए हम उन के शुरू और अंत फोन करता हूँ।
>> इसलिए हम मध्यबिंदु द्वारा गणना 0 प्लस 2 से विभाजित 14 जोड़ने;
बहुत सीधा मध्यबिंदु।
और हम कह सकते हैं कि मध्यबिंदु अब 7 है।
तो 15 के लिए हम देख रहे हैं क्या है?
नहीं यह नहीं।
हम 19 के लिए देख रहे हैं।
लेकिन हम 19 से अधिक है कि पता हम बीच में क्या मिला है।
>> तो हम क्या कर सकते हैं प्रारंभ बिंदु बदल
बस के अधिकार के लिए किया जाना है मध्य, और फिर इस प्रक्रिया को दोहराने।
हम ऐसा है, हम अब कहते हैं नई शुरुआत बिंदु सरणी स्थान 8 है।
क्या हम प्रभावी ढंग से किया है है 15 के बाईं ओर नजरअंदाज कर दिया सब कुछ।
हम आधे समाप्त कर दिया है समस्या की, और अब,
बजाय खोज के लिए होने का हमारे सरणी में 15 से अधिक तत्वों,
हम केवल 7 पर खोज करने के लिए है।
तो 8 नए प्रारंभ बिंदु है।
14 अभी भी अंत बिंदु है।
>> और अब, हम फिर से इस पर चलते हैं।
हम नए मध्यबिंदु गणना।
8 प्लस 14 2 11 से विभाजित, 22 है।
इस के लिए हम देख रहे हैं क्या है?
नहीं यह नहीं।
हम है कि एक मूल्य के लिए देख रहे हैं हम तो बस क्या पाया की तुलना में कम है।
इसलिए हम दोहराने के लिए जा रहे हैं फिर से प्रक्रिया।
हम करने के लिए अंत बिंदु को बदलने के लिए जा रहे हैं सिर्फ मध्यबिंदु के बाईं ओर हो।
इसलिए नए अंत बिंदु 10 हो जाता है।
और अब, इस बात का ही हिस्सा है सरणी के माध्यम से हम हल करना होगा।
तो क्या अब हम समाप्त कर दिया है 15 तत्वों की 12।
हम जानते हैं कि 19 कि अगर सरणी में मौजूद है, यह
तत्व के बीच कहीं न कहीं मौजूद होना चाहिए नंबर 8 और तत्व नंबर 10।
>> तो हम फिर से नया मध्यबिंदु गणना।
8 प्लस 10 2 9 से विभाजित, 18 है।
और इस मामले में, देखो, लक्ष्य मध्य में है।
हम देख रहे हैं कि वास्तव में क्या पाया।
रुक सकते हैं।
हम सफलतापूर्वक पूरा एक द्विआधारी खोज।
ठीक है।
इसलिए हम इस एल्गोरिथ्म जानते लक्ष्य है कि अगर काम करता है
कहीं सरणी के अंदर।
इस एल्गोरिथ्म काम करता है, तो करता है लक्ष्य सरणी में नहीं है?
ठीक है, चलो यह शुरू करते हैं फिर, और इस बार,
के तत्व के लिए देखो नेत्रहीन हम देख सकते हैं, जो 16,
सरणी में कहीं भी मौजूद नहीं है।
>> प्रारंभ बिंदु फिर 0 है।
अंत बिंदु फिर से 14 है।
उन पहले के सूचकांक हैं और पूरा सरणी के अंतिम तत्वों।
और हम इस प्रक्रिया में हम सिर्फ माध्यम से जाना होगा के माध्यम से चला गया, फिर से, 16 खोजने की कोशिश कर,
यहां तक ​​कि नेत्रहीन हालांकि, हम पहले से ही कर सकते हैं यह वहाँ नहीं होने जा रहा है कि बताओ।
हम सिर्फ यकीन है कि इस एल्गोरिथ्म बनाना चाहते वास्तव में, अभी भी किसी तरह से काम करेगा
और सिर्फ हमें छोड़ कर नहीं एक अनंत लूप में अटक गया।
>> तो कदम पहले क्या है?
मध्यबिंदु की गणना वर्तमान सरणी की।
मध्यबिंदु क्या है वर्तमान सरणी की?
खैर, यह सही है, 7 है?
2 से विभाजित 14 प्लस 0 7 है।
हम क्या देख रहे हैं 15 है?
नहीं।
यह बहुत करीब है, लेकिन हम देख रहे हैं कि तुलना में थोड़ा बड़ा एक मूल्य के लिए।
>> इसलिए हम यह करने के लिए जा रहा है कि पता है 15 के बाईं ओर कहीं नहीं हो।
लक्ष्य से अधिक है क्या मध्य में है।
और इसलिए हम नई शुरुआत बिंदु करने के लिए सेट सिर्फ बीच की सही करने के लिए किया जाना है।
मध्यबिंदु तो, वर्तमान में 7 की नई शुरुआत बिंदु 8 कहते हैं।
और हम प्रभावी रूप से क्या है फिर से किया नजरअंदाज कर दिया है
सरणी के पूरे बाईं आधा।
>> अब, हम दोहराने एक और बार की प्रक्रिया।
नई मध्यबिंदु गणना।
8 प्लस 14 2 11 से विभाजित, 22 है।
हम क्या देख रहे हैं 23 है?
दुर्भाग्यवश नहीं।
हम एक मूल्य के लिए देख रहे हैं कि कम से कम 23 है।
और हां, इस मामले में हम जा रहे हैं अंत बिंदु को बदलने के लिए बस हो
वर्तमान मध्यबिंदु के बाईं ओर।
वर्तमान मध्यबिंदु 11 है, और इसलिए हम नई अंत बिंदु निर्धारित करेंगे
हम अगली बार के लिए 10 के लिए इस प्रक्रिया के माध्यम से।
>> फिर, हम फिर से इस प्रक्रिया के माध्यम से जाना।
मध्यबिंदु गणना।
2 से विभाजित 8 प्लस 10 9 है।
हम क्या देख रहे हैं 19 है?
दुर्भाग्यवश नहीं।
हम अभी भी देख रहे हैं कि कम से कम एक नंबर।
इसलिए हम अंत बिंदु इस समय बदल देंगे सिर्फ मध्यबिंदु के बाईं ओर हो।
मध्य, वर्तमान में 9 है तो अंत बिंदु 8 हो जाएगा।
और अब, हम अभी देख रहे हैं एक ही तत्व सरणी में।
>> इस सरणी के मध्य बिंदु क्या है?
खैर, यह, 8 में शुरू होता है 8 पर समाप्त होता है, मध्यबिंदु 8 है।
कि हम के लिए क्या देख रहे हैं?
हम 17 के लिए देख रहे हैं?
नहीं, हम 16 के लिए देख रहे हैं।
यह सरणी में मौजूद है तो, यह कहीं न कहीं मौजूद होना चाहिए
हम वर्तमान में कर रहे हैं, जहां के बाईं ओर।
तो हम क्या करने जा रहे हैं?
खैर, हम तो बस होने के लिए अंत बिंदु निर्धारित करेंगे वर्तमान मध्यबिंदु के बाईं ओर।
इसलिए हम 7 के लिए अंत बिंदु बदल देंगे।
आप बस क्या देख रहे हो हालांकि, यहाँ क्या हुआ?
अब यहाँ देखो।
>> प्रारंभ अब अंत की तुलना में अधिक है।
प्रभावी ढंग से, दो सिरों हमारे सरणी के पार कर दी है,
और शुरू बिंदु है अब अंत बिंदु के बाद।
वैसे, यह नहीं करता है ठीक है, कोई मतलब?
तो अब, क्या हम कह सकते हैं कि हम है आकार 0 के एक उप सरणी है।
और एक बार हम करने के लिए मिल रहे हैं इस बिंदु पर, हम अब कर सकते हैं
उस तत्व की गारंटी 16 सरणी में मौजूद नहीं है,
प्रारंभ बिंदु क्योंकि और अंत बिंदु पार कर दी है।
और तो यह कुछ नहीं है।
अब, यह थोड़ा है कि नोटिस शुरू बिंदु और अंत की तुलना में अलग
एक ही बात की जा रही।
हम देख रहा था, तो 17 के लिए, यह होता है
सरणी, और शुरू बिंदु में किया गया कि अंतिम यात्रा की और अंत बिंदु
उन बिंदुओं को पार करने से पहले, हम वहाँ 17 पाया होता।
वे हम कर सकते हैं कि पार यह केवल जब तत्व नहीं है कि गारंटी
सरणी में मौजूद हैं।
>> तो चलो एक बहुत कम ले चलो रैखिक खोज से कदम।
सबसे खराब स्थिति में, हम था n तत्वों की सूची में ऊपर विभाजित करने के लिए
बार-बार छमाही में, लक्ष्य को खोजने के लिए क्योंकि या तो लक्ष्य तत्व
पिछले में कहीं हो जाएगा विभाजन, या यह सब पर मौजूद नहीं है।
सबसे खराब स्थिति में तो, हम करने के लिए है क्या तुम जानते हो array-- अलग है?
N बार के प्रवेश; हम समस्या में कटौती की है
आधा समय की एक निश्चित संख्या में।
समय की यह संख्या लॉग n है।
>> सबसे अच्छी स्थिति क्या है?
खैर, पहली बार हम मध्यबिंदु की गणना,
हम क्या देख रहे हो पाते हैं।
पिछले सभी में द्विआधारी खोज पर उदाहरण
हम था कि अगर हम सिर्फ पर चला गया है तत्व 15 के लिए तलाश कर दिया गया,
हम चाहते हैं कि तुरंत पाया होता।
यही कारण है कि बहुत शुरुआत में किया गया था।
कि midpoint था एक विभाजन में पहला प्रयास
द्विआधारी खोज में एक प्रभाग की।
>> और तो सबसे खराब में मामले, द्विआधारी खोज चलाता है
काफी बेहतर है, जो लॉग n में सबसे खराब स्थिति में रैखिक खोज, की तुलना में।
सबसे अच्छा मामले में, द्विआधारी खोज 1 की ओमेगा में चलाता है।
तो द्विआधारी खोज एक बहुत है रैखिक खोज की तुलना में बेहतर है,
लेकिन आप की प्रक्रिया के साथ सौदा किया है आप कर सकते हैं इससे पहले पहली बार अपने सरणी छँटाई
द्विआधारी खोज की शक्ति का लाभ उठाते हैं।
>> मैं डौग लॉयड हूँ।
इस सीएस 50 है।