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