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