[MUSIC پخش] 

ZAMYLA CHAN: اولین چیزی که شما ممکن است اطلاع در مورد پیدا کردن این است که ما در حال حاضر کد نوشته شده برای ما. این کد توزیع نامیده می شود. بنابراین ما نه فقط نوشتن خود ما کد از ابتدا دیگر. در عوض، ما در حال پر کردن فضاهای خالی در برخی از کد موجود از قبل. 

برنامه find.c دهید برای اعداد برای پر کردن کومه علف خشک، جستجو انبار کاه برای یک سوزن کاربر را مشاهده کنید، و این کار با تماس با مرتب کردن و جستجو، توابع تعریف شده در helpers.c. بنابراین find.c نوشته شده است در حال حاضر. کار شما این است که ارسال یاران. 

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

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

اما یک شرط وجود دارد. جستجوی دودویی تنها می توانید جستجو از طریق لیست های از پیش طبقه بندی شده اند. چرا؟ 

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

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

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

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

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

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

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

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

برای من برابر با 0، عنصر اول به n منهای 1، شما در حال رفتن به مقایسه هر مقدار بعدی پس از آن و پیدا کردن شاخص حداقل مقدار. هنگامی که شما در پیدا کردن مقدار شاخص حداقل، شما می توانید که مقدار آرایه مبادله حداقل و آرایه I. 

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

بنابراین کسانی که دو نمونه از نوع به الگوریتم های که شما می توانید برای اجرای برنامه پیدا کردن. هنگامی که شما به پایان مرتب کردن، و شما انجام جستجو، شما به پایان رسید. نام من Zamyla است، و این CS50 است. 

[MUSIC پخش]