آموزش جست‌وجوالگوریتم‌ها

۰۱ شرطی که هیچ‌جا نوشته نشده

جست‌وجوی دودویی یک پیش‌شرط دارد که هیچ تابعی بررسی‌اش نمی‌کند: فهرست باید مرتب باشد. اگر نباشد، bisect خطا نمی‌دهد، جواب غلط می‌دهد. برای کدی که در فهرست هست جای نبودن را برمی‌گرداند، و کد شما بی‌آنکه چیزی بفهمد پیام «مشتری یافت نشد» را چاپ می‌کند. این بدترین شکل ممکن یک باگ است، چون شکل یک نتیجه معتبر را دارد.

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

۰۲ و گاهی هیچ‌کدام از این دو

اگر فقط می‌پرسید «این کد هست یا نه» و به جایش کاری ندارید، هیچ‌کدام از این دو جواب درست نیست: یک مجموعه این را در زمان ثابت می‌گوید و مرتب بودن هم نمی‌خواهد. جست‌وجوی دودویی وقتی برنده است که به موقعیت هم نیاز داشته باشید، یا به نزدیک‌ترین قلم کوچک‌تر، یا به همه قلم‌های یک بازه. آن سه پرسش را مجموعه اصلا جواب نمی‌دهد و bisect هر سه را با یک فراخوانی می‌دهد.

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

۰۳ جایی که کار گیر می‌کند، جست‌وجو در فهرستی است که مرتب نیست

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

۰۴ ابزار، و سالی که این حرف درست است

در سال ۲۰۲۶ ماژول bisect در کتابخانه استاندارد و رایگان است و جای نوشتن حلقه دودویی دستی را گرفته، که رایج‌ترین جای اشتباه در محاسبه نقطه میانی و شرط پایان است. از پایتون 3.10 پارامتر key را هم دارد، یعنی می‌شود روی فهرستی از رکوردها بر اساس یک فیلد جست‌وجو کرد بدون اینکه ستون کلید را جدا استخراج کنید. برای وقتی که جواب فقط بله و خیر است، ظرف درست مجموعه است و به هیچ ماژولی نیاز ندارد.

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