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