عدد ‎$x$‎ و دنباله‌ی اعداد ‎$a_1 \leq a_2 \leq \dots \leq a_n$‎ داده شده است. ففلی می‌خواهد ببیند که ‎$x$‎ در این دنباله وجود دارد یا خیر. برای این کار از الگوریتم جستجوی دودویی (Binary Search) استفاده می‌کند. این الگوریتم به این صورت کار می‌کند که اگر بخواهیم در زیردنباله‌ی ‎$a_i \leq a_{i+1} \leq \dots \leq a_j$‎ به دنبال ‎$x$‎ بگردیم در ابتدا ‎$x$‎ را با ‎$a_{\lfloor (i+j)/2\rfloor}$‎ مقایسه کرده و بر اساس جواب به یکی از دو زیرمسئله‌ی بازگشتی کوچک‌ترِ ‎$(i‎, ‎\lfloor (i+j)/2\rfloor-1)$‎ و یا ‎$(\lfloor (i+j)/2\rfloor+1‎, ‎j)$‎ می‌رویم و یا در صورت برابری به الگوریتم پایان می‌دهیم.

به خاطر شیطنت‌های خاص ففلی، او در مقایسه‌ی ‎$x$‎ با هر ‎$a_i$‎ ممکن است اشتباه کند اما می‌دانیم که به ازای هر ‎$a_i$‎ او در عمر خود در مقایسه‌ی ‎$x$‎ با ‎$a_i$‎ حداکثر یک بار اشتباه می‌کند. ففلی الگوریتم فوق را ‎$k$‎ بار تکرار می‌کند. کم‌ترین مقدار ‎$k$‎ چند است به طوری‌که مطمئن باشیم در لااقل یک بار از این ‎$k$‎ بار ففلی به جواب درست می‌رسد.

• سوال بعد
• سوال قبل