المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۵:سوال ۲۹

سوال ۲۹

آرایه‌ی $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$ درست کار می‌کند؟

پاسخ

به عنوان مثال اگر اعداد ما ۴٬۱۰٬۲۰ و ۲ بوده و $x=20$ باشد به سادگی قابل بررسی است که این ااگوریتم در خروجی خود عدد $x=20$ را عضوی از آرایه‌ی $a$ معرفی نخواهد کرد.


ابزار صفحه