[संगीत बजाना] डौग लॉयड: रैखिक खोज के लिए एक एल्गोरिथ्म हम है एक सरणी में एक तत्व खोजने के लिए उपयोग कर सकते हैं। एक एल्गोरिथ्म रिकॉल एक कदम-दर-कदम सेट है एक कार्य को पूरा करने के लिए निर्देशों का। 

रैखिक खोज इस प्रकार के रूप एल्गोरिथ्म काम करता है। बाएं से सरणी पार पुनरावृति ठीक है, एक निर्दिष्ट तत्व की तलाश में। 

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

इसलिए हम 23 पर दिखेगा। हम क्या देख रहे हैं 23 है? अच्छी तरह से नहीं है, तो हम अगले कदम पर तत्व है, और अगले तत्व, और हम के माध्यम से जा रहा रखने और अधिक से अधिक इस प्रक्रिया और अधिक है, जब तक हम जमीन इस तरह की स्थिति पर। 

नौ, हम देख रहे हैं क्या है और सरणी के इस तत्व है, यह मूल्य नौ है। और इसलिए हम हम क्या कर रहे हैं पाया खोज रहा है, और हम नहीं रोक सकता। रैखिक खोज है सफलतापूर्वक पूरा। 

लेकिन हम के लिए क्या देख रहे हैं के बारे में हमारे सरणी में नहीं है कि एक तत्व। रैखिक खोज अभी भी काम करता है? तो यह बात पक्की। इसलिए हम इस प्रक्रिया को दोहराने पहला तत्व पर शुरू। यह हम क्या कर रहे है तो खोज रहा है, हम नहीं रोक सकता। यह। अन्यथा, हम अगले तत्व के लिए कदम। 

लेकिन हम इस प्रक्रिया को दोहरा रख सकते हैं बदले में प्रत्येक तत्व की जांच, हम नंबर 50 को लगता है कि उम्मीद है। लेकिन हम जानते हैं कि अगर नहीं होंगे हम संख्या 50 हो पाया है हम नहीं करते हैं, तो हम कदम रखा है जब तक सरणी के हर एक तत्व पर। 

केवल हम एक बार किया है और कहा कि, कम आए हम निष्कर्ष निकाल सकते हैं 50 सरणी में नहीं है। और तो रैखिक खोज एल्गोरिथ्म, यह विफल रहा है, ठीक है, दर असल। लेकिन नहीं अर्थों में यह है कि कर में असफल रहा था क्या हम उसे करने के लिए कहा। 

यह रूप में असफल रहा था यह 50 नहीं मिल रहा था के रूप में ज्यादा है, लेकिन 50 सरणी में नहीं था। लेकिन हम विस्तृत रूप से खोज की है हर एक तत्व के माध्यम से और हां, जब तक हम नहीं मिल रहा था कुछ भी हो, रैखिक खोज अभी भी सफल होता है, भले ही तत्व सरणी में नहीं है। 

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

इस बारे में क्या कहना है रैखिक खोज की जटिलता? खैर सबसे खराब स्थिति में, हम है हर एक तत्व को देखने के लिए। और तो यह हे में चलता है एन, सबसे खराब स्थिति में। 

सबसे अच्छा मामले में, हम कर रहे हैं तुरंत तत्व लगता है। और तो 1 के ओमेगा में चलाता है। 

मैं डौग लॉयड हूँ। इस CS50 है।