مقدمه
به گروهی از ریاضیدانها برخورد کردهاید که خواننده-ترانهسرا هم هستند.
آنها برای هر یک از اعداد مورد علاقهشان یک ترانه نوشتهاند و همانطور که میتوانید تصور کنید، اعداد مورد علاقهی زیادی دارند (مثل ۰ یا ۷۳ یا ۶۱۷۴).
کنجکاو هستید ترانهی عدد مورد علاقهی خودتان را بشنوید، اما با این همه ترانه که باید یکییکی بررسی کنید، پیدا کردن ترانهی درست ممکن است مدتی طول بکشد.
خوشبختانه، آنها ترانههایشان را در یک فهرست پخش مرتبشده بر اساس عنوان سازمان دادهاند؛ عنوان هم همان عددی است که ترانه دربارهی آن است.
متوجه میشوید که میتوانید از یک الگوریتم «جستوجوی دودویی» استفاده کنید تا با دانستن عنوان، ترانه را بهسرعت پیدا کنید.
دستورالعملها
وظیفهی شما پیادهسازی یک الگوریتم جستوجوی دودویی است.
الگوریتم جستوجوی دودویی عنصری را در یک فهرست پیدا میکند و برای این کار فهرست را بارها به دو نیم میکند و فقط نیمی را نگه میدارد که عنصر مورد نظر ما در آن قرار دارد.
این روش به ما اجازه میدهد مکانهای ممکن عنصرمان را بهسرعت محدود کنیم، تا آن را پیدا کنیم یا همهی مکانهای ممکن را از میان برداریم.
جستوجوی دودویی فقط زمانی کار میکند که فهرست مرتب شده باشد.
الگوریتم چنین است:
- عنصر میانی یک فهرست مرتبشده را پیدا کنید و آن را با عنصری که دنبالش میگردیم مقایسه کنید.
- اگر عنصر میانی همان عنصر مورد نظر ما باشد، کار تمام است!
- اگر عنصر میانی بزرگتر از عنصر مورد نظر ما باشد، میتوانیم آن عنصر و همهی عنصرهای بعد از آن را حذف کنیم.
- اگر عنصر میانی کوچکتر از عنصر مورد نظر ما باشد، میتوانیم آن عنصر و همهی عنصرهای قبل از آن را حذف کنیم.
- اگر همهی عنصرهای فهرست حذف شده باشند، آن عنصر در فهرست وجود ندارد.
- در غیر این صورت، همین روند را روی بخشی از فهرست که حذف نشده است تکرار کنید.
بیایید یک مثال ببینیم:
فرض کنید میخواهیم عدد ۲۳ را در فهرست مرتبشدهی زیر پیدا کنیم: [4, 8, 12, 16, 23, 28, 32].
- ابتدا ۲۳ را با عنصر میانی، یعنی ۱۶، مقایسه میکنیم.
- چون ۲۳ بزرگتر از ۱۶ است، میتوانیم نیمهی چپ فهرست را حذف کنیم و
[23, 28, 32] باقی میماند.
- سپس ۲۳ را با عنصر میانی جدید، یعنی ۲۸، مقایسه میکنیم.
- چون ۲۳ کوچکتر از ۲۸ است، میتوانیم نیمهی راست فهرست را حذف کنیم:
[23].
- عنصر مورد نظرمان را پیدا کردیم.
رفتار
راهحل شما باید در مورد موارد آزمون با رفتار توابع درونساخت searchsorted در Julia همخوانی داشته باشد.
یعنی بهجای برگرداندن اندیس اولین عنصر منطبقی که در فهرست پیدا میکنید، «بازه»ای را برمیگردانید که کران پایین آن اندیس اولین عنصر منطبق در فهرست است و کران بالای آن اندیس آخرین عنصر منطبق در فهرست.
با این حال، برای سادهتر کردن راهحلتان میتوانید فرض کنید که عنصر هدف تکرار نشده است، بهجز مجموعهآزمون امتیاز که به تطابقهای چندگانه میپردازد.
اگر عنصر جستوجوشده در فهرست نباشد، باید بازهای خالی برگردانید که کران پایین آن اندیسی است که آن عنصر میتواند در آن به فهرست مرتبشده درج شود. بازهی خالی هر بازهای است که کران بالای آن کمتر از کران پایین باشد.
برای جزئیات بیشتر، مستندات و مثالهای تابع searchsorted را بخوانید:
searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)
Return the range of indices of a which compare as equal to x (using binary
search) according to the order specified by the by, lt and rev keywords,
assuming that a is already sorted in that order.
Return an empty range located at the insertion point if a does not contain
values equal to x.
See also: insorted, searchsortedfirst, sort, findall.
Examples
julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
3:3
julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
4:5
julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3:2
julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6
julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0
امتیازها
- راهحل خود را گسترش دهید تا از آرگومانهای کلیدواژهای
by، lt و rev پشتیبانی کند، بهطوری که by تبدیلی را مشخص میکند که روی همهی عناصر فهرست اعمال میشود، lt یک مقایسه را مشخص میکند و rev مشخص میکند که آیا فهرست بهصورت معکوس مرتب شده است. وقتی این پارامترها به کار میروند، باید فرض کنید که فهرست از قبل با همین پارامترها مرتب شده است. برای جزئیات بیشتر، مستندات sort را ببینید.
- از فهرستهایی پشتیبانی کنید که عنصر هدف در آنها تکرار شده است (اولین و آخرین اندیسی را پیدا کنید که عنصر هدف با آنها برابر مقایسه میشود).
