مقدمه
به گروهی از ریاضی‌دان‌ها برخورد کرده‌اید که خواننده-ترانه‌سرا هم هستند.
آن‌ها برای هر یک از اعداد مورد علاقه‌شان یک ترانه نوشته‌اند و همان‌طور که می‌توانید تصور کنید، اعداد مورد علاقه‌ی زیادی دارند (مثل ۰ یا ۷۳ یا ۶۱۷۴).
کنجکاو هستید ترانه‌ی عدد مورد علاقه‌ی خودتان را بشنوید، اما با این همه ترانه که باید یکی‌یکی بررسی کنید، پیدا کردن ترانه‌ی درست ممکن است مدتی طول بکشد.
خوشبختانه، آن‌ها ترانه‌هایشان را در یک فهرست پخش مرتب‌شده بر اساس عنوان سازمان داده‌اند؛ عنوان هم همان عددی است که ترانه درباره‌ی آن است.
متوجه می‌شوید که می‌توانید از یک الگوریتم «جست‌وجوی دودویی» استفاده کنید تا با دانستن عنوان، ترانه را به‌سرعت پیدا کنید.
دستورالعمل‌ها
وظیفه‌ی شما پیاده‌سازی یک الگوریتم جست‌وجوی دودویی است.
الگوریتم جست‌وجوی دودویی با تقسیم مکرر یک فهرست به دو نیمه، عنصری را در آن پیدا می‌کند؛ به این ترتیب که فقط نیمه‌ای را نگه می‌دارد که عنصر مورد جست‌وجو در آن قرار دارد.
این کار به ما امکان می‌دهد جایگاه‌های ممکن عنصرمان را به‌سرعت محدود کنیم، تا آن را پیدا کنیم یا تا همه‌ی جایگاه‌های ممکن را از میان برداریم.
جست‌وجوی دودویی فقط زمانی کار می‌کند که فهرست مرتب شده باشد.
الگوریتم به این شکل است:
- عنصر میانی یک فهرست مرتب را پیدا کنید و آن را با عنصری که به دنبالش هستیم مقایسه کنید.
- اگر عنصر میانی همان عنصر ما باشد، کار تمام است!
- اگر عنصر میانی بزرگ‌تر از عنصر ما باشد، می‌توانیم آن عنصر و همه‌ی عناصر بعد از آن را حذف کنیم.
- اگر عنصر میانی کوچک‌تر از عنصر ما باشد، می‌توانیم آن عنصر و همه‌ی عناصر قبل از آن را حذف کنیم.
- اگر همه‌ی عناصر فهرست حذف شده باشند، آن عنصر در فهرست نیست.
- در غیر این صورت، همین روند را روی بخشی از فهرست که حذف نشده است تکرار کنید.
یک مثال:
فرض کنید در فهرست مرتب زیر به دنبال عدد ۲۳ هستیم: [4, 8, 12, 16, 23, 28, 32].
- کار را با مقایسه‌ی ۲۳ با عنصر میانی، یعنی ۱۶، شروع می‌کنیم.
- چون ۲۳ از ۱۶ بزرگ‌تر است، می‌توانیم نیمه‌ی چپ فهرست را حذف کنیم و
[23, 28, 32] برایمان می‌ماند.
- سپس ۲۳ را با عنصر میانی جدید، ۲۸، مقایسه می‌کنیم.
- چون ۲۳ از ۲۸ کوچک‌تر است، می‌توانیم نیمه‌ی راست فهرست را حذف کنیم:
[23].
- عنصرمان را پیدا کردیم.
