حل تشریحی سوال شماره 7 ساختمان داده ها و طراحی الگوریتم ها

فرض کنید آرایه‌ای از اعداد صحیح $A=\left[a_1;a_2;\dots a_n\right]$ داده شود. فرض کنید یک اندیس (ناشناخته) k وجود دارد به‌طوری که زیر آرایه $A=\left[a_1;a_2;\dots a_k\right]$ به‌ترتیب اکیدا افزیشی مرتب شده است و زیر آرایه $A=\left[a_k;a_{k+1};\dots a_n\right]$ به‌ترتیب اکیدا نزولی مرتب شده است (یعنی اگر $1\le i<j\le k$آنگاه $a_i<a_j$، و اگر $k\le i<j\le n$ ، آنگاه $a_i>a_j$ هدف شما تعیین k است. یک الگوریتم بهینه برای حل این مسئله چه زمان اجرایی دارد؟