یک ارایه n تایی از اعداد صحیح با شرط های زیر داده شده است
۱- [tex]A(1)=x,A(n)=y,x<y[/tex]
۲- [tex]\forall i \left | A(i)- A(i 1) \right |\leq 1[/tex]
یک الگوریتم کارا برای جستجوی w به طوری که [tex]x\leq w\leq y[/tex] در ازایه A طراحی شده است. این الگوریتم اندیس w را در صورت وجود به دست می آورد. پیچیدگی الگوریتم در بدترین حالت و حالت متوسط چیست

کتاب پوران به این سوال این جواب را داده که(صفحه ۱۴۴)
با توجه به شرط های بیان شده ارایه مرتب است و برای ارایه مرتب می توان ار جستجوی دودویی استفاده کردو این جستجو در بدترین حالت و حالت متوسط دارای پیچیدگی O(log(n می باشد
ولی اگر به شرط ها دقت کنیم لزومی ندارد ارایه مرتب باشد بلکه به نظر من در بهترین حالت ارایه مرتب است به عنوان مثال اگر فرض کنیم y=x+2 و n=6 باشد. یک مقدار برای ارایه از اندیس ۱ تا n به ترتیب از چپ به راست برابر است با
x-1,x,x-1,x,x+1,x+2
با این حساب جواب این سوال چیست؟