در این سوال شما بایستی توابع ‎lower_bound‎ و ‎upper_bound‎ را پیاده سازی کنید. فرض کنید قرار است شما این توابع را روی آرایه‌ی ‎ مرتب شده‎‎‎ شده از عناصری از یک تایپ به نام ‎C‎ اجرا کنید. در ضمن فرض کنید تابع ‎bool f(C a‎, ‎C b)‎ وجود دارد که در صورتی‌که ‎a<b‎‎، به عنوان خروجی ‎true و در غیر این‌صورت ‎false‎ برمی‌گرداند. شما بایستی تابع‎‎ C *lower_bound(C *first‎, ‎C *last‎, ‎C key)‎ ‎ را بنویسید. این تابع مشابه تابع lower_bound‎ عادی در بازه‌ی ‎first‎ تا ‎last‎ به دنبال ‎key‎ می‌گردد. برای مقایسه‌ی عناصر از تابع ‎f‎ استفاده می‌کند و اشاره‌گر به عنصری که پیدا می‌کند را بعنوان خروجی برمی‌گرداند. در ضمن اگر بین ‎first‎ و ‎last‎ ‎ تعداد ‎$n$ عنصر از تایپ ‎C‎ وجود داشته باشد این تابع باید در زمان ‎${\cal O}(\log{n})$‎ اجرا شود. به طور مشابه تابع ‎C *upper_bound(C *first‎, ‎C *last‎, ‎C key)‎ را بنویسید. ‎

‎ راهنمایی:‎ اگر f(a,b) ‎ برابر ‎false باشد و ‎f(b,a)‎ هم ‎false‎ باشد می‌توان نتیجه گرفت ‎a=b‎ است. ‎ ‎

نکته: اگر نمی‌توانید سوال بالا را حل کنید:‎ همین توابع را برای ‎int lower_bound(int l‎, ‎int r‎, ‎int key)‎ و ‎int uppper\_bound(int l‎, ‎int r‎, ‎int key)‎ بنویسید منتهی با این تفاوت که این توابع در آرایه‌ی ‎ مرتّب شده ‎a‎ که ‎global‎ و از نوع ‎int‎ است به دنبال key‎ می‌گردند و اندیس خانه‌ای که پیدا می‌کنند را بعنوان خروجی برمی‌گردانند.

• سوال قبل