الگوریتم جستجوی دودویی (Binary Search) یک الگوریتم جستجوی بنیادی است که به شما امکان می‌دهد یک مقدار هدف (Target value) را در یک آرایه مرتب‌شده (Sorted Array) با تقسیم مکرر لیست به دو نیمه پیدا کنید.
در واقع، جستجوی دودویی از نظر فنی به عنوان گسترشی از الگوی دو اشاره‌گر محسوب می‌شود، زیرا از یک اشاره‌گر چپ (Left Pointer) و یک اشاره‌گر راست (Right Pointer) استفاده می‌کند که لیست را گام به گام نصف می‌کنند.
در اینجا توضیحات عمیق‌تری در مورد جستجوی دودویی ارائه شده است:
۱. مکانیسم عملکرد و کارایی
- پیمایش کارآمد: جستجوی دودویی با نگاه کردن به عنصر میانی شروع می‌شود و بررسی می‌کند که آیا این عنصر، مقدار هدف است یا خیر.
- تصمیم‌گیری:
- اگر عنصر میانی همان هدف باشد، جستجو با موفقیت به پایان می‌رسد.
- اگر عنصر میانی کوچکتر از هدف باشد، می‌دانید که هدف باید جایی در سمت راست باشد، زیرا آرایه مرتب شده است؛ بنابراین، فرآیند را تنها روی نیمه راست تکرار می‌کنید.
- اگر عنصر میانی بزرگتر از هدف باشد، فرآیند روی نیمه چپ تکرار می‌شود.
- همگرایی: این فرآیند آنقدر تکرار می‌شود تا در نهایت به مقدار هدف همگرا شوید.
کارایی: این الگوریتم به دلیل تقسیم مکرر فضای جستجو، یک الگوریتم کارآمد است و به ما امکان می‌دهد تا هدف را در زمان لگاریتمی $O(\log n)$ پیدا کنیم، که بسیار بهتر از جستجوی خطی $O(n)$ است.
۲. کاربرد در توابع یکنوا (Monotonic Functions)
چیزی که جستجوی دودویی را فوق‌العاده قدرتمند می‌کند، این است که کاربرد آن فراتر از لیست‌های عددی مرتب‌شده است.
- شرط اصلی: جستجوی دودویی می‌تواند در هر لیستی استفاده شود که در آن یک تابع یکنوا (Monotonic Function) وجود داشته باشد.
- تعریف تابع یکنوا: یک تابع یکنوا هر نوع الگویی است که در آن افزایش یا کاهش ثابتی وجود دارد، و این تنها محدود به اعداد نیست.
- شرط مرتب‌سازی: به بیان ساده‌تر، ما به دنبال هر نوع شرایطی هستیم که بتوان از آن برای مرتب‌سازی استفاده کرد، نه صرفاً اعداد اکیداً صعودی.
مثال: جستجوی اولین وقوع “درست” (True)
فرض کنید یک لیست مرتب شده فقط شامل مقادیر “درست” (True) و “نادرست” (False) داشته باشیم. می‌توان از جستجوی دودویی برای پیدا کردن اولین وقوع “درست” استفاده کرد:
- شما به میانه لیست نگاه می‌کنید.
- اگر مقدار میانی درست باشد، می‌دانید که اولین وقوع “درست” باید در همین نقطه یا جایی در سمت چپ آن باشد، بنابراین جستجو را به نیمه چپ محدود می‌کنید.
- اگر مقدار میانی نادرست باشد، می‌دانید که اولین وقوع “درست” باید در سمت راست باشد، بنابراین روی نیمه راست تمرکز می‌کنید.
این نوع جستجو، که بر اساس اینکه یک شرط در کجا “درست” و در کجا “نادرست” است انجام می‌شود، می‌تواند برای هر مسئله جستجوی دودویی دیگری نیز استفاده شود.
۳. اعمال جستجوی دودویی در مسائل پیچیده
حتی مسائلی که در ابتدا به نظر نمی‌رسد از مرتب‌سازی پیروی کنند، می‌توانند با استفاده از مفهوم یکنواختی حل شوند.
- مثال (آرایه مرتب‌شده چرخشی): در مسئله یافتن کمترین مقدار در یک آرایه مرتب‌شده چرخشی (Minimum in Rotated Sorted Array)، در نگاه اول، آرایه مرتب به نظر نمی‌رسد.
- شرط یکنواختی: با این حال، یک شرط یکنواخت وجود دارد که می‌توان از آن استفاده کرد:
- هر عنصری که کوچکتر از آخرین عنصر آرایه باشد، بخشی از بخش چرخشی است.
- هر عنصری که بزرگتر از آخرین عنصر آرایه باشد، بخشی از بخش مرتب‌شده اصلی است.
- تبدیل به شرط درست/نادرست: می‌توان این شرط را در ذهن به مقادیر “درست” و “نادرست” تبدیل کرد و سپس از همان منطق جستجوی دودویی برای حل مسئله استفاده نمود.