سوال ۲۹

آرایه‌ی $a$ با $n$ عنصر به صورت صعودی مرتب شده است. می‌خواهیم ببینیم که آیا عنصر $x$ در آرایه‌ي $a$ وجود دارد یا خیر. برای این کار الگوریتم زیر را پیشنهاد می‌کنیم:

1. $i$ را مساوی ۱ و $j$ را مساوی با $n$ قرار بده.
2. $k$ را مساوی با $[\frac{i+j}{2}]$ قرار بده.
3. اگر $a_k < x$ ، در این صورت $i$ را مساوی با $k+1$ قرار بده٬ در غیر این صورت $j$ را مساوی با $k-1$ قرار بده.
4. اگر $a_k = x$ ، در این صورت $x$ در آرایه‌ي $a$ وجود دارد؛ به مرحله «۷» برو.
5. اگر $i \geq j$ ، در این صورت $x$ در آرایه‌ي $a$ وجود ندارد؛ به مرحله «۷» برو.
6. برو به مرحله‌ي «۲».
7. پایان.

آیا این الگوریتم برای تمام مقادیر $x$ درست کار می‌کند؟

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