>> [موسیقی]
>> داگ لوید: بسیار خوب.
بنابراین جستجوی دودویی یک IS الگوریتم ما می توانید استفاده کنید
برای پیدا کردن یک عنصر در داخل یک آرایه.
بر خلاف جستجوی خطی، آن نیاز به شرایط ویژه از قبل ملاقات کرد،
اما آن را بسیار بسیار کارآمد تر اگر که شرط این است، در واقع، ملاقات کرد.
>> پس چه این ایده در اینجا نیست.
آن را تقسیم و حل است.
ما می خواهیم به منظور کاهش حجم منطقه جستجو بر اساس نیم هر بار
در جهت پیدا کردن یک عدد هدف.
این که در آن شرایط است که به بازی می آید، هر چند.
ما فقط می توانیم اهرم قدرت حذف نیمی از عناصر
حتی بدون نگاه کردن آنها اگر آرایه مرتب شده است.
>> اگر آن را یک مخلوط کردن کامل، ما نمی توانیم فقط از دست
دور از نیمی از عناصر، به دلیل ما نمی دانیم که آنچه ما انجام داد.
اما اگر آرایه مرتب شده است، ما می توانیم انجام این کار، چون ما
مطمئن شوید که همه چیز به سمت چپ که در آن ما در حال حاضر
باید پایین تر از باشد ارزش ما در حال حاضر در آن هستید.
و همه چیز را به حق که در آن ما
باید بیشتر از مقدار باشد ما در حال حاضر به دنبال.
>> پس چه شبه است این مراحل را برای جستجوی دودویی؟
ما این روند را تکرار تا زمانی که آرایه یا، به عنوان ما را از طریق ادامه دهید،
آرایه های فرعی، قطعات کوچکتر آرایه اصلی است، از اندازه 0.
محاسبه نقطه میانی از آرایه زیر فعلی است.
>> اگر مقدار شما به دنبال برای است در آن عنصر از آرایه، را متوقف کند.
شما آن را در بر داشت.
عالیه.
در غیر این صورت، اگر هدف است کمتر از آنچه که در وسط،
بنابراین اگر ارزش ما به دنبال برای پایین تر از آنچه ما می بینیم،
دوباره این روند را تکرار، اما تغییر نقطه پایان، به جای
بودن اصلی کامل آرایه کامل،
به فقط به سمت چپ از جایی که ما فقط نگاه کرد.
>> ما می دانستیم که وسط خیلی بلند بود یا هدف کمتر از متوسط ​​بود،
و پس از آن باید وجود داشته باشد، اگر آن وجود دارد و در همه در آرایه،
جایی به سمت چپ از نقطه میانی.
و بنابراین ما آرایه مجموعه محل فقط به سمت چپ
از نقطه میانی به عنوان نقطه پایان است.
در مقابل، اگر هدف این است که بیشتر از چه چیزی در وسط،
ما یکسان انجام روند، اما به جای ما
تغییر نقطه شروع می شود فقط به سمت راست از نقطه میانی
ما فقط محاسبه می شود.
و پس از آن، ما این فرآیند را دوباره آغاز خواهد شد.
>> بیایید این تجسم، OK؟
بنابراین در بسیاری رفتن و در اینجا وجود دارد، اما در اینجا یک آرایه از 15 عنصر است.
و ما در حال رفتن به پیگیری از خیلی بیشتر مسائل این زمان.
بنابراین در جستجوی خطی، ما فقط مراقبت در مورد یک هدف است.
اما این بار ما می خواهیم در مورد مراقبت از جایی که ما
شروع به نگاه، که در آن در حال توقف ما به دنبال،
و چه از نقطه میانی است از آرایه جاری است.
بنابراین در اینجا ما با جستجوی دودویی است.
ما بسیار خوب به آن بروید، درسته؟
من فقط رفتن به از بین بردن زیر اینجا مجموعه ای از شاخص.
این است که اساسا فقط آنچه عنصر از آرایه ما در حال صحبت کردن در مورد.
با جستجوی خطی، ما مراقبت، تا آنجا که ما
باید بدانید که چگونه بسیاری از عناصر ما در حال تکرار بیش از،
اما ما در واقع مهم نیست چه عنصر ما در حال حاضر در به دنبال.
در جستجوی دودویی، کار می کنیم.
و به این ترتیب کسانی که فقط وجود دارد به عنوان یک راهنمای کوچک.
>> بنابراین ما می توانیم شروع، درست است؟
خوب، نه کاملا.
به یاد داشته باشید آنچه که من گفتم درباره جستجوی دودویی؟
ما می توانیم آن را در یک نمی آرایه نامرتب و یا دیگری،
ما تضمین نیست که عناصر و یا ارزش های معین نه
به طور تصادفی بودن دور انداخته زمانی که ما فقط
تصمیم به چشم پوشی از نیمی از آرایه.
>> بنابراین یک گام با جستجوی دودویی است که شما باید یک آرایه مرتب شده اند.
و شما می توانید هر یک از مرتب سازی استفاده الگوریتم های ما در مورد صحبت کردیم
به شما به آن موقعیت.
بنابراین در حال حاضر، ما در یک موقعیت که در آن هستید ما می توانیم جستجوی دودویی را انجام دهد.
>> بنابراین اجازه دهید این روند را تکرار گام به گام و نگه داشتن
آهنگ از آنچه اتفاق می افتد که ما بروید.
بنابراین در ابتدا ما نیاز به انجام است محاسبه از نقطه میانی آرایه جاری است.
خب، ما می گویند ما، اول از همه، به دنبال ارزش 19.
ما در حال تلاش برای پیدا کردن شماره 19.
این عنصر اولین بار از این آرایه است که در واقع شاخص صفر،
و آخرین عنصر از این آرایه است که در شاخص 14 واقع شده است.
و بنابراین ما آن شروع و پایان تماس بگیرید.
>> بنابراین ما محاسبه نقطه میانی توسط اضافه کردن 0 به علاوه 14 تقسیم بر 2.
نقطه میانی بسیار ساده.
و می توان گفت که از نقطه میانی است در حال حاضر 7.
بنابراین 15 چیزی است که ما به دنبال آن هستید؟
نه اینطور نیست.
ما به دنبال 19.
اما می دانیم که 19 بیشتر است از آنچه که ما در وسط پیدا شده است.
>> بنابراین آنچه که ما می توانید انجام دهید این است تغییر نقطه شروع
به فقط به سمت راست از نقطه میانی، و دوباره تکرار روند.
و هنگامی که ما انجام این کار، ما در حال حاضر می گویند که نقطه شروع جدید موقعیت آرایه 8 است.
چه ما به طور موثر انجام داده ام همه چیز را نادیده گرفته به سمت چپ از 15.
ما نیم حذف از مشکل، و در حال حاضر،
به جای داشتن به جستجو بیش از 15 عناصر آرایه ما،
ما فقط باید به جستجو بیش از 7.
بنابراین 8 نقطه شروع جدید است.
14 هنوز نقطه پایان است.
>> و در حال حاضر، ما بیش از این دوباره.
ما محاسبه نقطه میانی است.
8 به علاوه 14 22، تقسیم بر 2 11 است.
آیا این چیزی است که ما به دنبال آن هستید؟
نه اینطور نیست.
ما به دنبال یک ارزش است که کمتر از آنچه که ما فقط پیدا شده است.
بنابراین ما قصد داریم به تکرار این فرآیند را دوباره.
ما در حال رفتن به تغییر نقطه به نقطه فقط به سمت چپ از نقطه میانی.
بنابراین نقطه پایان جدید 10 شود.
و اکنون، که تنها بخشی از آرایه ما باید به مرتب سازی از طریق.
بنابراین ما در حال حاضر حذف 12 نفر از 15 عنصر است.
ما می دانیم که اگر 19 در آرایه وجود دارد، آن
باید جایی بین عنصر وجود داشته باشد شماره 8 و عنصر شماره 10.
>> بنابراین ما از نقطه میانی جدید دوباره محاسبه کند.
8 به علاوه 10 18 است، تقسیم بر 2 9 است.
و در این مورد، نگاه کنید، هدف این است که در وسط.
ما در بر داشت چیزی است که ما دنبال آن هستید.
ما می توانیم را متوقف کند.
ما با موفقیت به اتمام یک جستجوی دودویی.
خیلی خوب.
بنابراین ما این الگوریتم مطمئن شوید کار می کند اگر هدف
جایی در داخل آرایه است.
آیا این کار الگوریتم اگر هدف این است که در آرایه نیست؟
خوب، اجازه دهید آن را شروع دوباره، و این زمان،
اجازه دهید برای این عنصر نگاه 16، که به صورت بصری ما می توانید ببینید
کند در آرایه وجود در هر نقطه.
>> نقطه شروع دوباره 0.
نقطه پایان است دوباره 14.
کسانی که شاخص از اولین و عناصر آخرین آرایه کامل است.
و ما در این روند ما فقط از طریق رفت دوباره، تلاش برای پیدا کردن 16،
حتی اگر بصری، ما در حال حاضر می توانید بگویید که آن را نمی وجود داشته باشد.
ما فقط می خواهیم مطمئن شوید این الگوریتم خواهد شد، در واقع، هنوز هم در برخی از راه کار
و نه فقط به ما ترک در یک حلقه بی نهایت گیر کرده است.
>> پس چه گام اول است؟
محاسبه نقطه میانی از آرایه جاری است.
از نقطه میانی چه خبر از آرایه در حال حاضر؟
خوب، آن را 7، درست است؟
14 به علاوه، 0 تقسیم بر 2 7 است.
15 چیزی که ما دنبال آن هستید؟
شماره
آن را بسیار نزدیک، اما ما به دنبال برای یک مقدار کمی بزرگتر از آن است.
>> بنابراین ما می دانیم که آن را به هیچ جا به سمت چپ 15.
هدف بزرگتر از آنچه در نقطه میانی است.
و بنابراین ما تنظیم نقطه شروع جدید به فقط به سمت راست از وسط.
از نقطه میانی در حال حاضر 7، پس اجازه دهید بگویم نقطه شروع جدید 8 است.
و آنچه که ما به طور موثر دوباره انجام نادیده گرفته
کل نیمه سمت چپ آرایه.
>> در حال حاضر، ما در تکرار پردازش یک بار دیگر.
محاسبه نقطه میانی است.
8 به علاوه 14 22، تقسیم بر 2 11 است.
23 چیزی که ما دنبال آن هستید؟
متاسفانه نه.
ما به دنبال یک ارزش که کمتر از 23 است.
و بنابراین در این مورد، ما قصد داریم به تغییر نقطه پایان به فقط
به سمت چپ از نقطه میانی فعلی است.
از نقطه میانی در حال حاضر 11 است، و بنابراین ما به نقطه پایان جدید مجموعه
برای دفعه بعد ما از طریق این فرایند به 10.
>> باز هم، ما را از طریق فرایند دوباره.
محاسبه نقطه میانی.
8 به علاوه 10 تقسیم بر 2 9 است.
19 چیزی که ما دنبال آن هستید؟
متاسفانه نه.
ما هنوز به دنبال تعداد کمتر از آن است.
بنابراین ما به نقطه پایان این زمان را تغییر دهید به فقط به سمت چپ از نقطه میانی.
از نقطه میانی در حال حاضر 9، بنابراین نقطه پایان خواهد بود 8.
و در حال حاضر، ما فقط به دنبال در یک آرایه عنصر.
>> از نقطه میانی این آرایه چیست؟
خوب، آن را در 8 شروع می شود، آن را در 8 به پایان می رسد، نقطه میانی 8 است.
چیزی است که ما دنبال آن هستید؟
آیا ما برای 17 به دنبال؟
نه، ما به دنبال 16.
بنابراین اگر آن را در آرایه وجود دارد، آن را باید در جایی وجود داشته باشد
در سمت چپ که در آن ما در حال حاضر می باشد.
بنابراین چه می خواهیم کاری انجام دهید؟
خب، ما نقطه پایان مجموعه به فقط به سمت چپ از نقطه میانی فعلی است.
بنابراین ما به نقطه پایان به 7 تغییر دهید.
آیا شما آنچه فقط ببینید در اینجا اتفاق افتاده، هر چند؟
نگاه کردن در اینجا در حال حاضر.
>> شروع در حال حاضر بیشتر از پایان.
به طور موثر، دو سر آرایه ما عبور کرده اند،
و نقطه شروع است اکنون پس از نقطه پایان است.
خب، که نمی هر گونه احساس، درست است؟
بنابراین در حال حاضر، آنچه که ما می گویند ما است باید یک آرایه زیر از اندازه 0.
و یک بار ما به بدست این مرحله، ما هم اکنون می توانید
تضمین کند که عنصر 16 در آرایه وجود ندارد،
چون نقطه شروع و نقطه پایان عبور کرده اند.
و پس از آن وجود ندارد.
در حال حاضر، توجه کنید که این است که کمی متفاوت از نقطه شروع و پایان
نقطه بودن همان.
اگر ما دنبال شده است 17، آن ​​را
در آرایه، و نقطه شروع شده و نقطه پایان از این تکرار آخرین
قبل از آن نقطه عبور، ما در بر داشت 17 وجود دارد.
این تنها زمانی که آنها عبور که ما می توانیم تضمین کند که عنصر نیست
در آرایه وجود دارد.
>> بنابراین اجازه دهید به مقدار زیادی کمتر مراحل نسبت به جستجوی خطی.
در بدترین حالت، ما تا به حال به تقسیم کردن یک لیست از عناصر N
بارها و بارها در نیمه به پیدا کردن هدف، یا به این دلیل عنصر هدف
خواهد در جایی در گذشته باشد تقسیم، و یا آن را در تمام وجود ندارد.
بنابراین در بدترین حالت، ما به تقسیم تا آرایه را می شناسید؟
ورود به سیستم از N بار؛ ما مجبور به قطع مشکل
در یک و نیم تعداد معینی از بار.
که تعداد دفعاتی ورود n است.
>> بهترین حالت چه خبر؟
خب، اولین بار ما محاسبه نقطه میانی،
ما پیدا کردن آنچه ما دنبال آن هستید.
در تمام قبلی نمونه هایی در جستجوی دودویی
ما فقط بیش رفته است، اگر ما به حال شده است برای این عنصر 15 به دنبال،
ما که بلافاصله پیدا کرده اند.
که در ابتدا.
که از نقطه میانی بود اولین تلاش در یک تقسیم
از یک بخش در جستجوی دودویی.
>> و به این ترتیب در بدترین مورد، جستجوی دودویی اجرا می شود
در log n است، که قابل ملاحظه ای بهتر از جستجوی خطی، در بدترین حالت.
در بهترین حالت، باینری جستجو اجرا می شود در امگا، از مجموع 1
بنابراین جستجوی دودویی زیادی است بهتر از جستجوی خطی،
اما شما باید برای مقابله با روند مرتب سازی آرایه خود را برای اولین بار شما می توانید قبل
اهرم قدرت جستجوی دودویی.
>> من داگ لوید هستم.
این CS 50 است.