مقدمه
به گروهی از ریاضی‌دان‌ها برخورد کرده‌اید که خواننده-ترانه‌سرا هم هستند.
آن‌ها برای هر یک از اعداد مورد علاقه‌شان یک ترانه نوشته‌اند و همان‌طور که می‌توانید تصور کنید، اعداد مورد علاقه‌ی زیادی دارند (مثل ۰ یا ۷۳ یا ۶۱۷۴).
کنجکاو هستید ترانه‌ی عدد مورد علاقه‌ی خودتان را بشنوید، اما با این همه ترانه که باید یکی‌یکی بررسی کنید، پیدا کردن ترانه‌ی درست ممکن است مدتی طول بکشد.
خوشبختانه، آن‌ها ترانه‌هایشان را در یک فهرست پخش مرتب‌شده بر اساس عنوان سازمان داده‌اند؛ عنوان هم همان عددی است که ترانه درباره‌ی آن است.
متوجه می‌شوید که می‌توانید از یک الگوریتم «جست‌وجوی دودویی» استفاده کنید تا با دانستن عنوان، ترانه را به‌سرعت پیدا کنید.
دستورالعمل‌ها
وظیفه‌ی شما پیاده‌سازی یک الگوریتم جست‌وجوی دودویی است.
الگوریتم جست‌وجوی دودویی عنصری را در یک فهرست پیدا می‌کند و برای این کار فهرست را بارها به دو نیم می‌کند و فقط نیمی را نگه می‌دارد که عنصر مورد نظر ما در آن قرار دارد.
این روش به ما اجازه می‌دهد مکان‌های ممکن عنصرمان را به‌سرعت محدود کنیم، تا آن را پیدا کنیم یا همه‌ی مکان‌های ممکن را از میان برداریم.
جست‌وجوی دودویی فقط زمانی کار می‌کند که فهرست مرتب شده باشد.
الگوریتم چنین است:
- عنصر میانی یک فهرست مرتب‌شده را پیدا کنید و آن را با عنصری که دنبالش می‌گردیم مقایسه کنید.
- اگر عنصر میانی همان عنصر مورد نظر ما باشد، کار تمام است!
- اگر عنصر میانی بزرگ‌تر از عنصر مورد نظر ما باشد، می‌توانیم آن عنصر و همه‌ی عنصرهای بعد از آن را حذف کنیم.
- اگر عنصر میانی کوچک‌تر از عنصر مورد نظر ما باشد، می‌توانیم آن عنصر و همه‌ی عنصرهای قبل از آن را حذف کنیم.
- اگر همه‌ی عنصرهای فهرست حذف شده باشند، آن عنصر در فهرست وجود ندارد.
- در غیر این صورت، همین روند را روی بخشی از فهرست که حذف نشده است تکرار کنید.
بیایید یک مثال ببینیم:
فرض کنید می‌خواهیم عدد ۲۳ را در فهرست مرتب‌شده‌ی زیر پیدا کنیم: [4, 8, 12, 16, 23, 28, 32].
- ابتدا ۲۳ را با عنصر میانی، یعنی ۱۶، مقایسه می‌کنیم.
- چون ۲۳ بزرگ‌تر از ۱۶ است، می‌توانیم نیمه‌ی چپ فهرست را حذف کنیم و
[23, 28, 32] باقی می‌ماند.
- سپس ۲۳ را با عنصر میانی جدید، یعنی ۲۸، مقایسه می‌کنیم.
- چون ۲۳ کوچک‌تر از ۲۸ است، می‌توانیم نیمه‌ی راست فهرست را حذف کنیم:
[23].
- عنصر مورد نظرمان را پیدا کردیم.
پیام‌های استثنا
گاهی لازم است که یک استثنا ایجاد کنید. وقتی این کار را می‌کنید، همیشه باید یک پیام خطای معنادار هم همراه آن بگذارید تا نشان دهید منبع خطا چیست. این کار code شما را خواناتر می‌کند و به debugging کمک زیادی می‌کند. در موقعیت‌هایی که می‌دانید منبع خطا از یک نوع مشخص است، می‌توانید یکی از انواع خطای داخلی را ایجاد کنید، اما همچنان باید پیام معناداری همراه آن بگذارید.
این تمرین به‌طور خاص از شما می‌خواهد که با استفاده از دستور raise یک ValueError را «پرتاب» کنید، وقتی مقداری که داده شده در آرایه پیدا نمی‌شود. tests تنها زمانی قبول می‌شوند که هم exception را raise کنید و هم پیامی همراه آن بگذارید.
برای اینکه یک ValueError همراه با پیام ایجاد کنید، پیام را به‌عنوان آرگومان به نوع exception بدهید:
# example when value is not found in the array.
raise ValueError("value not in array")
