====== سوال ۱۰ ======

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

  * [[سوال ۹|سوال قبل]]