[موسیقی] داگ لوید: خطی جستجو، الگوریتم است می توانید برای پیدا کردن یک عنصر در یک آرایه استفاده کنید. فراخوان الگوریتم مجموعه ای گام به گام است از دستورالعمل برای انجام یک کار. 

جستجو خطی الگوریتم کار شرح زیر است. تکرار در سراسر آرایه از چپ به حق، به دنبال یک عنصر مشخص شده است. 

در شبه است، که یک بیشتر نسخه مقطر از این جمله، اگر عنصر اولین چیزی است که شما به دنبال برای، شما می توانید متوقف شود. در غیر این صورت، حرکت به عنصر بعدی و رفتن بارها و بارها تا شما در پیدا کردن این عنصر، یا شما نمی کنند. بنابراین ما می توانیم خطی استفاده الگوریتم جستجو، برای مثال، برای پیدا کردن مقدار هدف نه در این آرایه است. خب ما در آغاز شروع می شود. اگر آن چیزی است که ما به دنبال، ما می تواند به توقف. آن را نه، ما برای 11 به دنبال ندارد. بنابراین در غیر این صورت، به عنصر بعدی حرکت می کند. 

بنابراین ما در 23 نگاه کنید. 23 چیزی که ما دنبال آن هستید؟ خب نه، بنابراین ما به بعدی حرکت می کند عنصر، و عنصر بعدی، و ما را از طریق این فرایند و بیش از بیش و بیش از، تا زمانی که ما زمین در وضعیت مثل این. 

نه چیزی است که ما به دنبال آن هستید، و این عنصر از آرایه است، ارزش آن نه است. و بنابراین ما در بر داشت چیزی است که ما به دنبال، و ما می توانیم را متوقف کند. جستجو خطی تکمیل شده، با موفقیت. 

اما آنچه در مورد اگر ما به دنبال برای یک عنصر است که در آرایه ما نیست. آیا هنوز هم جستجوی خطی کار می کند؟ خب مطمئن شوید. بنابراین ما این روند را تکرار با شروع در عنصر اول. اگر آن چیزی است که ما به دنبال، ما می تواند به توقف. این طور نیست. در غیر این صورت، ما به عنصر بعدی حرکت می کند. 

اما ما می توانیم به تکرار این روند، بررسی هر یک از عناصر به نوبه خود، به این امید که ما تعداد 50 پیدا کنید. اما ما نمی خواهد می دانم که اگر ما تعداد 50 پیدا کردم و یا اگر ما نمی، تا زمانی که ما پا بیش از هر عنصر از آرایه. 

تنها یک بار انجام داده ایم که و آمد تا کوتاه، می توانید نتیجه می گیریم که 50 در آرایه نیست. و به این ترتیب جستجوی خطی الگوریتم، به خوبی از آن شکست خورده، در هر سه. اما نه به این معنا که آن را ناموفق در انجام شد آنچه که ما آن را خواسته به انجام. 

آن را در عنوان ناموفق بود اندازه آن 50 را پیدا کند، اما 50 در آرایه بود. اما ما جامع جستجو از طریق هر عنصر و به همین ترتیب، در حالی که ما را پیدا کند هر چیزی، جستجوی خطی هنوز هم موفق حتی اگر عنصر در آرایه نیست. 

پس چه بدترین حالت است سناریو با جستجوی خطی؟ خوب ما را از طریق نگاه هر عنصر، یا به این دلیل عنصر هدف آخرین عنصر آرایه است، و یا عنصر ما به دنبال نمی کند در واقع در آرایه در همه وجود دارند. بهترین حالت چه خبر؟ خوب ما ممکن است پیدا کردن عنصر بلافاصله. و چگونه بسیاری از عناصر پس آیا باید به دنبال در در بهترین حالت، اگر ما به دنبال آن و ما آن را پیدا کنید در ابتدا؟ ما بلافاصله تواند متوقف شود. 

این به چه می گویند در مورد پیچیدگی جستجوی خطی؟ خب در بدترین حالت، ما باید به هر عنصر است. و پس از آن در ای اجرا می شود N، در بدترین حالت. 

در بهترین حالت، ما میخوایم پیدا کردن عنصر بلافاصله. و به این ترتیب در امگا، از مجموع 1 اجرا می شود. 

من داگ لوید هستم. این CS50 است.