در این سوال شما بایستی توابع 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 می‌گردند و اندیس خانه‌ای که پیدا می‌کنند را بعنوان خروجی برمی‌گردانند.