>> आरओबी BOWDEN: हाय, मैं रोब हूँ.
हम कैसे एक द्विआधारी खोज को काम करते हो?
चलो पता करते हैं.
तो, इस खोज से हम जा रहे हैं कि ध्यान दें बारी बारी से लागू करने के लिए.
तुम भी द्विआधारी खोज लागू कर सकता है iteratively, तो आप किया है कि अगर,
कि पूरी तरह से ठीक है.
>> अब सबसे पहले, याद करते हैं क्या खोज करने के लिए पैरामीटर के लिए होती हैं.
यहाँ, हम है जो इंट मूल्य देखते हैं, उपयोगकर्ता के मूल्य होना चाहिए
के लिए खोज.
हम int मूल्यों सरणी, जो देखने हम कर रहे हैं, जिसमें सरणी है
मूल्य के लिए खोज.
और हम है, जो int n देखना हमारे सरणी की लंबाई.
>> अब, पहली बात यह है कि पहले.
हम में N, 0 के बराबर होती है, तो देखने के लिए जाँच हम वापसी झूठी, जिस स्थिति.
हम एक खाली है, तो वह सिर्फ कह रहा है सरणी, मूल्य एक में स्पष्ट रूप से नहीं है
खाली सरणी, तो हम झूठे लौट सकते हैं.
>> अब, हम वास्तव में बाइनरी क्या करना चाहते हैं द्विआधारी खोज की खोज भाग.
तो, हम मध्य मिल चाहते हैं इस सरणी का तत्व.
यहाँ, हम मध्य विभाजित n के बराबर होती है कहना 2 से, मध्य तत्व है के बाद से
की लंबाई होने जा रहा हमारे सरणी 2 से विभाजित.
अब हम यह देखने के लिए जाँच करने के लिए जा रहे हैं मध्य तत्व हम कर रहे हैं मूल्य के बराबर होती है
के लिए खोज.
मानों मध्यम मूल्य के बराबर होती है यदि हां, तो हम हमने पाया क्योंकि सच लौट सकते हैं
हमारे सरणी में मान.
>> लेकिन यह सच नहीं था, तो अब हम पुनरावर्ती करने की ज़रूरत है
द्विआधारी खोज के कदम.
हम या तो खोज की जरूरत सरणी की या करने के लिए छोड़ दिया
सरणी के बीच.
बीच में मूल्यों है अगर तो यहाँ, हम कहते हैं मूल्य की तुलना में कम है, जो कि मूल्य का मतलब
मध्यम से अधिक था सरणी की.
इसलिए मूल्य का सही करने के लिए होना चाहिए हम बस पर देखा कि तत्व.
>> तो यहाँ, हम करने जा रहे हैं बारी बारी से खोज.
और हम हम गुजर रहे हैं पर देख लेंगे एक सेकंड में यह करने के लिए.
लेकिन हम करने के लिए खोज करने के लिए जा रहे हैं मध्य तत्व की सही.
और दूसरे मामले में, इसका मतलब है कि मूल्य के बीच से भी कम था
सरणी, और इसलिए हम जा रहे हैं बाईं ओर खोज करने के लिए.
अब बाईं होने जा रहा है थोड़ा आसान को देखने के लिए.
तो, हम हम बारी बारी से कर रहे हैं कि यहाँ देख जहां पहले खोज बुला
तर्क, फिर, मान है हम पर देख रहे हैं.
दूसरा तर्क होने जा रहा है हम पर खोज कर रहे थे कि सरणी.
और पिछले तत्व अब मध्य है.
पिछले पैरामीटर हमारे int है याद रखें एन, कि हमारे सरणी की लंबाई है तो.
>> खोज करने के लिए पुनरावर्ती कॉल में, हम कर रहे हैं अब कह रही है कि की लंबाई
सरणी बीच है.
तो, हमारी सरणी का आकार 20 और हम में से था अगर मध्य के बाद से, सूचकांक 10 में खोजा
20 2 से विभाजित है, कि हम कर रहे हैं इसका मतलब नए रूप में 10 गुजर
हमारे सरणी की लंबाई.
याद रखें कि आप एक सरणी है जब लंबाई 10 की, कि मान्य का मतलब
तत्वों 0 से 9 तक सूचकांकों में हैं.
तो यह हम चाहते हैं कि वास्तव में क्या है बाईं - हमारे अद्यतन सरणी निर्दिष्ट
मध्य तत्व से सरणी.
>> तो, सही करने के लिए तलाश है थोड़ा और अधिक मुश्किल.
अब सबसे पहले, की दूरी पर विचार करते हैं के अधिकार के लिए सरणी की
मध्य तत्व.
तो, हमारी सरणी आकार n का था, तो नई सरणी आकार n ऋण का हो जाएगा
मध्य शून्य से 1.
तो, के एन शून्य से बीच की सोचते हैं.
>> फिर, सरणी का आकार 20 के थे और हम मध्य पाने के लिए 2 से विभाजित,
इसलिए बीच फिर 10, एन शून्य से मध्यम है हमें 10 है, इसलिए 10 देने जा रहा है
बीच के अधिकार के लिए तत्वों.
लेकिन हम भी इस शून्य है 1, हम नहीं करना चाहते क्योंकि
बीच में ही शामिल हैं.
तो एन शून्य से मध्यम शून्य से 1 हमें देता है सही करने के लिए तत्वों की कुल संख्या
सरणी में मध्य सूचकांक की.
>> अब यहाँ, याद है कि मध्यम पैरामीटर मान सरणी है.
यहाँ तो, हम एक गुजर रहे हैं अद्यतन मूल्यों सरणी.
यह मूल्यों के साथ साथ मध्य प्लस 1 है वास्तव में बारी बारी से कह फोन
खोज, एक नई सरणी में गुजर रहा है, जहां कि नई सरणी मध्य में शुरू होता है
प्लस हमारे मूल मान सरणी में से एक.
>> उस के लिए एक वैकल्पिक वाक्यविन्यास, अब है कि आप है, संकेत देखने के लिए शुरू कर दिया है
एम्परसेंड मूल्यों मध्य प्लस 1.
इसलिए, बीच का पता हड़पने मूल्यों के साथ साथ एक तत्व.
>> अब, आप सहज नहीं थे आप की तरह है कि एक सरणी संशोधित
भी उपयोग कर यह लागू हो सकता था एक पुनरावर्ती सहायक समारोह, जहां
कि सहायक समारोह लेता है अधिक तर्क.
तो बजाय सिर्फ मान लेने की, सरणी, और सरणी के आकार,
सहायक समारोह में अधिक समय लग सकता है कम सूचकांक सहित तर्कों,
आप सरणी में के बारे में परवाह है कि और कि तुम ध्यान से ऊपरी सूचकांक
सरणी के बारे में.
>> और इसलिए दोनों कम का ट्रैक रखने सूचकांक और ऊपरी सूचकांक, तुम नहीं करते
कभी संशोधित करने की आवश्यकता मूल मान सरणी.
तुम बस के लिए जारी रख सकते हैं मानों सरणी का उपयोग करें.
लेकिन यहां हम एक सहायक की जरूरत नहीं है नोटिस जब तक हम कर रहे हैं के रूप में कार्य
मूल को संशोधित करने के लिए तैयार मानों सरणी.
हम में पारित करने के लिए तैयार हैं एक अद्यतन मूल्यों.
>> अब, हम पर द्विआधारी खोज नहीं कर सकते unsorted है कि एक सरणी.
तो, चलो इस हल करते हैं.
अब, कि तरह अतीत है नोटिस दो पैरामीटर है, जो मूल्यों int
हम छँटाई कर रहे हैं कि सरणी, और int n, सरणी की लंबाई है जो कि
हम छँटाई कर रहे हैं.
तो, यहाँ हम लागू करना चाहते हैं एक छँटाई कलन विधि
n के ओ चुकता है.
आप बुलबुला तरह, चयन चुन सकते हैं क्रमबद्ध करें, या सम्मिलन सॉर्ट, या
हम नहीं है कुछ अन्य प्रकार क्लास में देखा.
लेकिन यहाँ, हम करने जा रहे हैं चयन प्रकार का उपयोग.
>> तो, हम पुनरावृति करने के लिए जा रहे हैं पूरे सरणी से अधिक.
खैर, हम यहाँ हम पुनरावृति रहे हैं कि देखने 0 से n करने के लिए शून्य से 1.
क्यों नहीं सभी तरह से पता करने के लिए ऊपर?
खैर, हम पहले से ही हल है कि अगर पहले फिर n शून्य से 1 तत्वों,
पहले से ही होना चाहिए क्या बहुत पिछले तत्व सही जगह में, तो खत्म छँटाई
पूरे सरणी.
>> अब, याद कैसे चयन सॉर्ट काम करता है.
हम पूरे सरणी पर जाने के लिए जा रहे हैं में न्यूनतम मूल्य की तलाश
सरणी और छड़ी कि शुरुआत में.
तो फिर हम पूरे पर जाने के लिए जा रहे हैं सरणी फिर दूसरे की तलाश में
छोटी तत्व, और छड़ी कि में दूसरे स्थान पर
सरणी, और इतने पर.
तो, कि यह क्या कर रहा है है.
>> यहाँ, हम हम कर रहे हैं कि देख रहे हैं वर्तमान न्यूनतम सेटिंग
मैं वें सूचकांक के लिए मूल्य.
इसलिए पहली यात्रा पर, हम जा रहे हैं न्यूनतम मूल्य होने पर विचार करने के लिए
हमारे सरणी की शुरुआत.
फिर, हम पर पुनरावृति करने जा रहे हैं करने के लिए जाँच सरणी, का शेष
वहाँ की तुलना में किसी भी तत्व के रूप में बड़ा अगर देखना हम वर्तमान में कर रहे हैं कि एक
न्यूनतम पर विचार.
>> तो यहाँ, जम्मू प्लस एक मान - कि है वर्तमान में हम क्या कर रहे हैं से भी कम
न्यूनतम पर विचार.
तो फिर हम अद्यतन करने के लिए जा रहे हैं हम कम से कम करने के लिए है
सूचकांक जम्मू प्लस 1.
तो, पूरे सरणी पार करना है कि, और इस के बाद पाश, न्यूनतम के लिए
से न्यूनतम तत्व होना चाहिए सरणी में मैं वें स्थिति.
>> हम चाहते हैं कि एक बार जब हमें स्वैप कर सकते हैं मैं वें स्थिति में न्यूनतम मूल्य
सरणी में.
तो यह सिर्फ एक मानक स्वैप है.
हम एक अस्थायी मूल्य में दुकान - सरणी में मैं वें मूल्य -
सरणी में मैं वें मूल्य में डाल वहाँ है कि न्यूनतम मूल्य,
और फिर जहां में वापस की दुकान हुआ करते थे मौजूदा न्यूनतम मूल्य
सरणी में मैं वें मूल्य, तो हम इसे खोना नहीं था कि.
>> तो, उस पर जारी है अगली यात्रा.
हम दूसरे की तलाश शुरू कर देंगे न्यूनतम मूल्य और उस में डालने
दूसरे स्थान पर.
तीसरी यात्रा पर, हम देख लेंगे तीसरा न्यूनतम मूल्य और सम्मिलित
कि तीसरी स्थिति में है, और इसलिए हम एक हल सरणी है जब तक पर.
मेरा नाम रोब है, और इस चयन के आधार पर क्रमबद्ध किया गया था.