>> ROB BOWDEN: سلام، من راب هستم.
چگونه ما از یک جستجوی دودویی؟
بیایید پیدا کردن.
بنابراین، توجه داشته باشید که این جستجو ما در حال رفتن برای پیاده سازی به صورت بازگشتی.
شما همچنین می توانید جستجوی دودویی پیاده سازی تکرار، بنابراین اگر شما کار را انجام دادیم،
که کاملا خوب است.
>> در حال حاضر برای اولین بار، اجازه دهید به یاد داشته باشید آنچه را که پارامتر به جستجو به منظور باشد.
در اینجا، ما ارزش بین المللی است که ببینید تصور می شود ارزش به کاربر است
جستجو برای.
ما می بینیم آرایه مقادیر بین المللی، که آرایه است که در آن ما است
جستجو برای ارزش.
و ما می بینیم اعضای هیات n که طول آرایه است.
>> در حال حاضر، اولین چیزی که برای اولین بار.
ما چک کنید اگر n برابر 0 و در که در این صورت ما بازگشت کاذب.
که فقط گفت: اگر ما خالی آرایه، ارزش است که به وضوح در نمی
آرایه خالی، بنابراین ما می توانیم نادرست بازگشت.
>> در حال حاضر، ما در واقع می خواهیم انجام دهیم دودویی جستجو بخشی از جستجوی دودویی.
بنابراین، ما می خواهیم برای پیدا کردن وسط عنصر این آرایه.
در اینجا، ما می گویند وسط برابر است با N تقسیم 2، از عنصر وسط است
رفتن به طول آرایه ما تقسیم بر 2.
در حال حاضر ما در حال رفتن به چک کنید اگر عنصر وسط برابر است با ارزش ما
جستجو برای.
بنابراین اگر ارزش متوسط ​​برابر است با ارزش، ما می تواند به راست از ما در بر داشت
مقدار در آرایه است.
>> اما اگر که شد درست نیست، در حال حاضر ما نیاز به انجام بازگشتی
مرحله از جستجوی دودویی.
ما نیاز به جستجو یا به سمت چپ آرایه یا به
وسط آرایه.
بنابراین در اینجا، ما می گویند اگر ارزش ها در وسط است کمتر از ارزش، که بدان معنی است که مقدار
بیشتر از متوسط ​​بود از آرایه.
بنابراین مقدار باید در سمت راست باشد عنصری است که ما فقط نگاه کرد.
>> بنابراین در اینجا، ما قصد داریم به جستجو به صورت بازگشتی.
و ما در آنچه ما در حال عبور نگاه این در یک ثانیه.
اما ما قصد داریم برای جستجو به راست عنصر وسط.
و در مورد دیگر، که بدان معنی است که ارزش کمتر از وسط بود
آرایه و غیره ما در حال رفتن برای جستجو به سمت چپ.
در حال حاضر، سمت چپ است برای رفتن به کمی ساده تر نگاه کنید.
بنابراین، ما در اینجا ببینید که ما به صورت بازگشتی است تماس جست و جو که در آن برای اولین بار
بحث، دوباره، ارزش ما به دنبال بیش از.
آرگومان دوم است برای رفتن به مجموعه ای که ما بیش از جستجوی شد.
و آخرین عنصر در حال حاضر متوسط ​​است.
به یاد داشته باشید آخرین پارامتر از نوع int ما نفر، به طوری که طول آرایه ما است.
>> در تماس بازگشتی را برای جستجو، ما هستیم در حال حاضر گفت که طول
مجموعه ای متوسط ​​است.
بنابراین، اگر آرایه ما از اندازه 20 و ما بود جستجو در صفحه 10، از متوسط ​​است
20 تقسیم بر 2، که به معنی ما پس از 10 عنوان جدید
طول آرایه است.
به یاد داشته باشید که زمانی که شما یک آرایه طول 10، این بدان معناست که معتبر
عناصر در شاخص های 0 تا 9 می باشد.
بنابراین این دقیقا همان چیزی است که ما به خواهید مشخص به روز شده در آرایه ما - سمت چپ
مجموعه ای از عنصر وسط.
>> بنابراین، به دنبال حق است کمی مشکل تر است.
در حال حاضر برای اولین بار، اجازه دهید طول در نظر از آرایه به سمت راست
عنصر وسط.
بنابراین، اگر آرایه ما از نفر اندازه بود، پس از آن مجموعه ای جدید از سایز n منفی می شود
منهای متوسط ​​1.
بنابراین، اجازه دهید از n منهای وسط فکر می کنم.
>> باز هم، اگر آرایه ای از اندازه 20 و ما 2 تقسیم به دریافت وسط،
تا وسط 10، و سپس N منهای متوسط ​​است به ما 10 تا 10 را
عناصر در سمت راست وسط.
اما ما همچنین این منفی دارند 1، از آنجایی که ما نمی خواهند
عبارتند از وسط خود را.
بنابراین N منهای وسط منهای 1 به ما می دهد تعداد کل عناصر را به سمت راست
از شاخص متوسط ​​در آرایه.
>> حالا در اینجا، به یاد داشته باشید که وسط پارامتر آرایه ارزش است.
بنابراین در اینجا، ما در حال عبور به روز شده در آرایه ارزش.
این مقادیر به علاوه به علاوه متوسط ​​1 است در واقع گفت: به صورت بازگشتی تماس بگیرید
جستجو، عبور در یک آرایه جدید، که در آن که آرایه ای جدید در وسط شروع می شود
به علاوه یکی از اصلی آرایه ارزش های ما.
>> یک ترکیب جایگزین برای که، در حال حاضر که شما آغاز شده اید برای دیدن اشاره گر است،
ارزش علامت به علاوه وسط 1.
بنابراین، گرفتن آدرس از وسط به علاوه یک عنصر از ارزش ها.
>> در حال حاضر، اگر شما راحت نیست اصلاح یک آرایه مانند آن، شما
همچنین می تواند با استفاده از پیاده سازی یک تابع کمک بازگشتی، که در آن
که تابع کمک کننده طول می کشد استدلال است.
بنابراین به جای در نظر گرفتن فقط ارزش، آرایه و اندازه آرایه،
تابع کمکی می تواند بیشتر استدلال، از جمله شاخص های پایین تر
که شما می توانید در مورد در آرایه مراقبت و شاخص بالای مراقبت از شما
در مورد آرایه.
>> و به این ترتیب پیگیری هر دو پایین شاخص و شاخص بالا، شما نمی
نیاز به همیشه تغییر ارزش های اصلی آرایه.
شما فقط می توانید به ادامه استفاده از آرایه ارزش.
اما در اینجا، توجه ما را یاور لازم نیست عمل تا زمانی که ما هستیم
مایل به تغییر اصلی مقادیر آرایه.
ما مایل به تصویب در است ارزش ها به روز شد.
>> در حال حاضر، ما نمی توانیم جستجوی دودویی بیش از یک آرایه است که جستجوی ساده و عادی.
بنابراین، اجازه دهید این مرتب کردن.
در حال حاضر، توجه کنید که مرتب سازی بر گذشته است دو پارامترهای اعضای هیات ارزش است، که
مجموعه ای که ما در حال طبقه بندی، و int N، است که طول آرایه است که
ما در حال مرتب سازی.
بنابراین، در اینجا ما می خواهیم برای اجرای یک الگوریتم مرتب سازی
که ای از n مربع.
شما می توانید به مرتب سازی حبابی، انتخاب را انتخاب کنید مرتب کردن بر اساس، و یا مرتب سازی بر درج و یا
نوعی دیگر ما ندارد در کلاس دیده می شود.
اما در اینجا، ما قصد داریم به استفاده از انتخاب مرتب سازی بر.
>> بنابراین، ما قصد داریم به تکرار در کل آرایه.
خوب، در اینجا ما می بینیم که ما در حال تکرار از 0 تا n منهای 1.
چرا تمام راه را تا به N؟
خوب، اگر ما در حال حاضر طبقه بندی شده اند ام اولین N منهای 1 عناصر، پس از آن
آخرین عنصر آنچه در حال حاضر باید در محل صحیح، به طوری که مرتب سازی بر
کل آرایه.
>> در حال حاضر، به یاد داشته باشید که چگونه انتخاب مرتب سازی بر کار می کند.
ما قصد داریم تا بیش از کل آرایه به به دنبال حداقل مقدار در
آرایه و چوب است که در آغاز.
پس از آن ما قصد داریم در کل به آرایه دوباره به دنبال دوم
کوچکترین عنصر، و چوب است که در جایگاه دوم در
آرایه، و غیره.
بنابراین، این چیزی است که این انجام شده است.
>> در اینجا، ما می بینیم که ما هستیم تنظیم حداقل در حال حاضر
ارزش به شاخص i ام.
بنابراین در تکرار اول، ما قصد داریم به در نظر گرفتن حداقل به
شروع آرایه است.
سپس، ما قصد داریم به تکرار بیش از باقی مانده از آرایه، چک کردن به
ببینید اگر هر کدام از عناصر وجود دارد کوچکتر از است که ما در حال حاضر است
با توجه به حداقل برساند.
>> بنابراین در اینجا، ارزش J به علاوه یک - که کمتر از آنچه که ما در حال حاضر
با توجه به حداقل برساند.
پس از آن ما قصد داریم برای به روز رسانی چه ما فکر می کنیم حداقل به است
صفحه اول J به علاوه 1.
بنابراین، انجام این کار در سراسر آرایه، و بعد از این حلقه، حداقل
باید حداقل عنصر از است موقعیت i ام در آرایه.
>> زمانی که ما از آن، ما می توانیم مبادله حداقل مقدار را در موقعیت i ام
در آرایه.
بنابراین این فقط یک مبادله استاندارد.
ما در یک مقدار به طور موقت ذخیره - مقدار i ام در آرایه -
قرار داده و به مقدار i ام در آرایه حداقل ارزش است که متعلق وجود دارد،
و سپس ذخیره را که در آن مقدار حداقل فعلی استفاده می شود
مقدار i ام در آرایه، پس که ما آن را از دست دادن نیست.
>> بنابراین، ادامه می دهد که در تکرار بعدی.
ما شروع به دنبال دوم حداقل ارزش و وارد است که به
مقام دوم.
در تکرار سوم، ما به دنبال ارزش حداقل سوم و درج
که به مقام سوم، و غیره تا زمانی که ما یک آرایه مرتب شده است.
نام من راب است و این انتخاب مرتب سازی بر بود.