جست‌وجوی دودویی فقط پیدا کردنِ یک نسخه از عدد نیست. برای دادهٔ تکراری، مرزِ چپ و راست پاسخ می‌دهند همهٔ نسخه‌ها در کدام بازهٔ اندیسی هستند و محلِ درج کجاست. این تمرین دو حلقهٔ مستقل می‌سازد، invariantِ آن‌ها را کنترل می‌کند و محلِ درج را با عضویت یکی نمی‌گیرد.
سه صفر در یک آرایهٔ مرتب
آرایهٔ اصیل [−۲،۰،۰،۰،۳،۷] از قبل مرتب است. برای پرس‌وجوی صفر، lower bound اندیس۱ وupper bound اندیس۴ است؛ بنابراین بازهٔ نیمه‌بازِ [۱،۴) سه عضو دارد. upper bound اندیسِ خودِ آخرین صفر نیست؛ اولین جایگاهِ بعد از تمامِ صفرهاست.
اگر هدف۱ باشد، دو مرز به یک نقطه می‌رسند، چون۱ در داده وجود ندارد. این نقطه هنوز محلِ درجِ معتبر است. برای عضویت باید جدا بررسی کنیم مرزِ چپ داخلِ آرایه است و مقدارِ آن با هدف برابر است؛ وجودِ یک عددِ اندیسی، اثباتِ پیدا شدنِ هدف نیست.
دو قراردادِ متفاوت برای تساوی
در lower bound، هر عضوِ پیش از lo باید کوچک‌تر از هدف باشد و هر عضوِ از hi به بعد بزرگ‌تر یا مساویِ هدف. بازهٔ نامعلومِ [lo,hi) را با mid می‌شکنیم. اگر مقدارِ میانی کوچک‌تر باشد، lo به mid+۱ می‌رود؛ در غیر این صورت hi برابر mid می‌شود.
در upper bound، سمتِ چپ اجازهٔ تساوی دارد و سمتِ راست باید بزرگ‌تر باشد. پس هنگامِ برابریِ مقدارِ میانی با هدف نیز lo را جلو می‌بریم. همین تفاوتِ کوچک، مرزِ بعد از تمامِ تکرارها را می‌سازد؛ دو تابعِ یکسان با نامِ متفاوت پاسخِ درست نمی‌دهند.
دفترِ حلقه را بررسی کنیم
هر گام، lo وhi پیشین، mid، مقدارِ میانی و بازهٔ بعدی را در JSON ثبت می‌کند. پس از تغییرِ هر مرز، شرطِ بخشِ قطعیِ چپ و راست با بررسیِ مستقیمِ داده کنترل می‌شود. بازهٔ نامعلوم کوچک می‌شود و در lo=hi، جایگاهِ مرزی حاصل می‌شود.
این assertهای آموزشی تمامِ بخش‌هایی از آرایه را می‌خوانند. اعتبارسنجیِ مرتب‌بودنِ ورودی نیز پیمایش دارد؛ بنابراین کلِ wrapperِ این تمرین را صرفاً O(log n) نمی‌نامیم. ادعایِ لگاریتمی مربوط به تعدادِ تقسیم‌های حلقهٔ دودویی است، نه هزینهٔ همهٔ کنترل‌های اضافهٔ فایل.
oracle، مقدارِ مرز را با شمارش می‌گیرد
برای مرزِ چپ، تعدادِ اعضایِ کوچک‌تر از هدف را با پیمایشِ مستقیم می‌شماریم؛ برای مرزِ راست، تعدادِ اعضایِ کوچک‌تر یا مساوی. سپس دو پاسخ با bisect_left وbisect_right کتابخانهٔ استانداردِ Python نیز مقایسه می‌شوند. این کتابخانه در کنترل واقعاً اجرا شده است.
تمامِ آرایه‌های مرتبِ ساخته‌شده از صفر،یک ودو با طولِ صفر تا۶ و پنج پرس‌وجوی−۱تا۳ اجرا می‌شوند؛۴۲۰جفتِ آرایه وپرس‌وجو کنترل شده است. آرایهٔ خالی، همه‌برابر، قبلِ کمینه و بعدِ بیشینه داخلِ این مجموعه حضور دارند.
شمارشِ یک بازهٔ مقدار
برای تعدادِ اعضایِ بینِ low وhigh با دو سرِ شامل، مرزِ چپِ low را از مرزِ راستِ high کم می‌کنیم. همهٔ۱٬۲۶۰موردِ بازهٔ مقدار در جهانِ کوچک، با شمارشِ مستقیمِ low≤v≤high برابر شده‌اند. این کار جمعِ مقدارها یا به‌روزرسانیِ داده نیست؛ فقط تعدادِ اعضایِ ثابتِ داخلِ بازه است.
فایل، آرایهٔ نامرتب، پرس‌وجویِ بولین و عضوِ بولین را رد می‌کند. سقفِ محلی۳۲عضوِ صحیح و قدرمطلقِ ۱۰۰۰ است؛ داده پنهانی مرتب یا تغییر داده نمی‌شود. درخت فنویک جمعِ بازه با تغییرِ نقطه را پاسخ می‌دهد و صفحه‌بندیِ keyset قراردادِ پایگاهِ داده دارد. ادامه در مبانی هوش مصنوعی؛ این تمرین آزمونِ سرعتِ سامانهٔ واقعی نیست.
فایل تمرین و منبع
کد مستقلِ تمرین و کنترل‌ها؛ Python · ورودی‌ها و تمام خروجی واقعیِ همین تمرین؛ JSON
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.