جست‌وجوی دودویی

دستورالعمل‌ها

وظیفه‌ی شما پیاده‌سازی یک الگوریتم جست‌وجوی دودویی است.

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

الگوریتم چنین است:

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

بیایید یک مثال ببینیم:

فرض کنید می‌خواهیم عدد ۲۳ را در فهرست مرتب‌شده‌ی زیر پیدا کنیم: [4, 8, 12, 16, 23, 28, 32].

• ابتدا ۲۳ را با عنصر میانی، یعنی ۱۶، مقایسه می‌کنیم.
• چون ۲۳ بزرگ‌تر از ۱۶ است، می‌توانیم نیمه‌ی چپ فهرست را حذف کنیم و [23, 28, 32] باقی می‌ماند.
• سپس ۲۳ را با عنصر میانی جدید، یعنی ۲۸، مقایسه می‌کنیم.
• چون ۲۳ کوچک‌تر از ۲۸ است، می‌توانیم نیمه‌ی راست فهرست را حذف کنیم: [23].
• عنصر مورد نظرمان را پیدا کردیم.

پیوست

برای این تمرین در track کلوژر، می‌توانید فرض کنید ورودی یک بردار است، همان‌طور که تست‌ها نشان می‌دهند.

---

منبع

Wikipedia