====== جست‌و‌جوی عدد در جدول ======


یک جدول $n\times n$، شامل اعداد طبیعی و یک ماشین مقایسه‌گر در اختیار داریم. می‌دانیم در این جدول، اعداد در هر سطر و در هر ستون به صورت اکیدا صعودی مرتب شده‌اند. می‌خواهیم عدد $k$ را در جدول جست‌وجو کنیم. برای این کار در هر مرحله، می‌توانیم یک کارت شامل دو عدد $i$ و $j$ به ماشین بدهیم و ماشین با گرفتن این کارت به ما پاسخ می‌دهد که عددی که در خانه‌ی سطر $i$ و ستون $j$ قرار دارد، بزرگ‌تر، کوچک‌تر، یا مساوی $k$ است. روشی ارائه دهید که با حداکثر $2n-1$ کارت ورودی مشخص کند که $k$ در این جدول وجود دارد یا نه؛ و در صورت وجود $k$، جای آن را در جدول مشخص کند.

روش خود را با پاسخ به سوالات زیر بیان کنید و درستی آن را ثابت کنید:

  * با چه کارتی شروع می‌کنید؟
  * بعد از دادن هر کارت و با توجه به جوابی که ماشین می‌دهد، چه کارتی را به ماشین می‌دهید؟

  * [[سوال ۳|سوال بعد]]
  * [[سوال ۱|سوال قبل]]