You are not allowed to perform this action

جستجو در فضای شیطنت

عدد $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$ بار ففلی به جواب درست می‌رسد.