در آرایه ۳، ۷، ۱۲، ۱۸، ۲۵، ۳۱ و ۴۲ دنبال عدد ۲۵ هستیم. اگر از ابتدا همه خانه‌ها را بررسی کنیم، به پنجمین خانه می‌رسیم. اما با جست‌وجوی دودویی، ابتدا سراغ وسط می‌رویم و بخشی از آرایه را که پاسخ نمی‌تواند در آن باشد کنار می‌گذاریم. شرط مهم این مثال، مرتب بودن صعودی آرایه است.
برای فهم الگوریتم، حفظ کردن چند خط کد کافی نیست. باید بتوانید در هر مرحله بگویید مرز چپ و راست کجاست، چرا یک نیمه حذف می‌شود و چه زمانی جست‌وجو پایان می‌یابد. جدول اجرای دستی، این سه پرسش را به‌خوبی روشن می‌کند.
مرتب بودن، دلیل حذف نیمه آرایه است
در آرایه صعودی، اگر مقدار وسط از هدف کوچک‌تر باشد، مقدارهای سمت چپ آن هم نمی‌توانند پاسخ باشند. بنابراین جست‌وجو به سمت راست محدود می‌شود. اگر مقدار وسط بزرگ‌تر باشد، سمت راست حذف می‌شود. تعریف جست‌وجوی دودویی در واژه‌نامه NIST نیز بر تقسیم پی‌درپی بازه جست‌وجو در آرایه مرتب تکیه دارد.
اگر ترتیب داده‌ها نامعلوم باشد، این استدلال معتبر نیست. مثلاً در آرایه ۳، ۲۵، ۷، ۱۸ و ۴۲، کوچک‌تر بودن مقدار وسط از ۲۵ ثابت نمی‌کند که پاسخ سمت راست است؛ عدد ۲۵ در سمت چپ قرار دارد. این مثال کوتاه برای شروع یک ارائه درسی مفید است، چون ضرورت پیش‌شرط را نشان می‌دهد.
اندیس و مقدار را در دو ردیف جدا بنویسید
برای آرایه هفت‌عضوی ابتدا، اندیس‌ها از صفر تا شش هستند. مقدار ۱۸ در اندیس سه و مقدار ۲۵ در اندیس چهار قرار دارد. در جدول اجرا، مقایسه روی مقدار انجام می‌شود، اما مرزها با اندیس تغییر می‌کنند. مخلوط شدن این دو، یکی از علت‌های رایج اشتباه در توضیح الگوریتم است.
در این مثال، بازه شامل هر دو مرز است. وسط برابر بخش صحیح عبارت «چپ به‌علاوه نصف اختلاف راست و چپ» در نظر گرفته می‌شود. پس از مقایسه ناموفق، خانه وسط نیز از بازه بعدی کنار می‌رود؛ چون همان خانه بررسی شده است.
| مرحله | چپ | راست | وسط | مقدار وسط | تصمیم برای هدف ۲۵ |
|---|---|---|---|---|---|
| ۱ | ۰ | ۶ | ۳ | ۱۸ | چپ به ۴ تغییر می‌کند |
| ۲ | ۴ | ۶ | ۵ | ۳۱ | راست به ۴ تغییر می‌کند |
| ۳ | ۴ | ۴ | ۴ | ۲۵ | پاسخ در اندیس ۴ پیدا می‌شود |
سه مقایسه در این ورودی انجام شد. این عدد نتیجه همین مثال است و نباید به همه آرایه‌ها تعمیم داده شود. اگر هدف همان مقدار وسط اولیه بود، در اولین بررسی پیدا می‌شد.
مثال پیدا نشدن را هم اجرا کنید
حالا در همان آرایه دنبال ۲۰ بگردید. مرحله اول، مقدار ۱۸ باعث می‌شود چپ به چهار برسد. در مرحله دوم، مقدار ۳۱ راست را به چهار می‌رساند. در مرحله سوم، مقدار ۲۵ بزرگ‌تر از هدف است و راست به سه تغییر می‌کند. اکنون چپ چهار و راست سه است؛ بازه خالی شده و پاسخ وجود ندارد.
شرط ادامه در این قرارداد مرزی، کوچک‌تر یا مساوی بودن چپ نسبت به راست است. اگر از قرارداد بازه نیمه‌باز استفاده کنید، قواعد دیگری لازم است. این دو شیوه را در یک کد یا یک ارائه مخلوط نکنید. بهتر است ابتدا یکی را کامل بفهمید و بعد تفاوت آن‌ها را بررسی کنید.
سه خطا را با ورودی کوچک پیدا کنید
اولین خطا، قرار دادن چپ برابر وسط پس از کوچک‌تر بودن مقدار وسط است. در بعضی بازه‌های کوتاه، این کار پیشرفت ایجاد نمی‌کند و حلقه ممکن است تکرار شود. دومین خطا، بررسی نکردن آرایه خالی است. سومین خطا، فرض یکتا بودن پاسخ در داده دارای مقدار تکراری است.
اگر چند خانه مقدار ۲۵ داشته باشند، نسخه معمول جست‌وجوی دودویی ممکن است یکی از آن‌ها را برگرداند. پیدا کردن اولین یا آخرین رخداد، نیازمند تغییر هدف و قواعد ادامه جست‌وجوست. در عنوان تمرین مشخص کنید «وجود مقدار» را می‌خواهید یا «اولین محل آن» را؛ پاسخ این دو مسئله الزاماً یکسان نیست.
مرتب‌سازی را از هزینه جست‌وجو جدا ببینید
پیچیدگی زمانی جست‌وجوی دودویی روی آرایه با دسترسی مستقیم، لگاریتمی است، اما آماده‌سازی داده رایگان نیست. برای یک جست‌وجوی تنها روی داده نامرتب، باید هزینه مرتب‌سازی را هم در تصمیم حساب کنید. وقتی بارها روی مجموعه مرتب جست‌وجو می‌کنید، مسئله متفاوت می‌شود. ادعای «همیشه سریع‌تر» بدون مشخص کردن شرایط دقیق نیست.
یک ارائه کوتاه با مشارکت مخاطب بسازید
چهار بخش کافی است: پیش‌شرط، مثال موفق، مثال ناموفق و خطای مرزی. پیش از نمایش تصمیم هر مرحله، از مخاطب بخواهید نیمه بعدی را انتخاب کند. برای تمرین پایانی، آرایه تک‌عضوی و آرایه دارای عدد تکراری بدهید تا یادگیری فقط به مثال هفت‌عضوی محدود نماند.
پاورپوینت جست‌وجوی دودویی یک فایل ارائه قابل بررسی برای این موضوع است. جدول اجرای خودتان را به آن اضافه کنید و ترتیب اسلایدها را با زمان کلاس هماهنگ کنید. اگر جست‌وجوی دودویی را در کنار جست‌وجوی گراف مطرح می‌کنید، مطلب ارائه الگوریتم‌های BFS و DFS کمک می‌کند تفاوت مسئله‌ها را روشن نگه دارید؛ این الگوریتم‌ها صرفاً نام‌های متفاوت یک روش واحد نیستند.
