נתונה מטריצה בגודל \(m \times n\) אשר איברי כל שורה בה ממויינים בסדר עולה משמאל לימין, ואיברי כל עמודה בה ממויינים בסדר עולה מלמעלה למטה.
לדוגמה:

10, 20, 30, 40, 50
15, 25, 35, 45, 52
27, 29, 37, 48, 55
32, 33, 39, 58, 60

א. כתבו אלגוריתם המקבל כקלט את המטריצה ומספר \(K\), ומחזיר את מיקומו (שורה ועמודה) של \(K\) במטריצה. אם \(K\) אינו קיים במטריצה, האלגוריתם יחזיר מיקום המציין אי-מציאה. זמן הריצה הנדרש הוא \(\Theta(m+n)\). יש להסביר את נכונות האלגוריתם.

ב. כתבו אלגוריתם המקבל כקלט את המטריצה ומספר \(K\). האלגוריתם מכניס את \(K\) במקום האיבר המקסימלי במטריצה, ולאחר מכן מתקן אותה כך שתכונת המיון של השורות והעמודות תישמר. זמן הריצה הנדרש הוא \(\Theta(m+n)\). יש להסביר את נכונות האלגוריתם.
הדרכה: חשבו היכן נמצא האיבר המקסימלי. נסו להחליף אותו ב-\(K\) ולתקן את המטריצה על ידי הזזת איברים.