חיפוש במערך ממוין-סיבובית

בשאלה זו נתייחס למערכים דו-ממדיים ריבועיים, כלומר, מספר השורות והעמודות שווה וכזה שהוא חזקה של 2.

לצורך השאלה, נגדיר חלוקה פנימית של המערך לארבעה רביעים בגודל n/2 x n/2, ממוספרים מ-1 עד 4 באופן הבא:

נאמר שהמערך הוא סיבובי (circular) אם כל האיברים ברביע 1 קטנים ממש מכל אלו שברביע 2, אלו שברביע 2 קטנים ממש מכל אלו שברביע 3, ואלו שברביע 3 קטנים ממש מכל אלו שברביע 4. למשל, המערך הבא הוא סיבובי:

לשם הנוחות, נגדיר גם כל מערך בגודל 1×1 כמערך סיבובי. נאמר שמערך בגודל n×n הוא ממוין-סיבובית (circular sorted) אם הוא סיבובי, ארבעת הרביעים שלו הם סיבוביים, וכן הלאה עד לרביעים בגודל 1×1. לדוגמה, המערך הבא ממוין-סיבובית:

עליכם לכתוב שיטת חיפוש בינארית למימוש החיפוש במערך ממוין-סיבובית. השיטה מקבלת כפרמטרים את מערך דו-ממדי mat הוא ממוין-סיבובית, וערך לחיפוש num. אם הערך num נמצא במערך mat, השיטה יוחזר true ויודפסו מספר השורה ומספר העמודה שבהם נמצא המספר num. אם הערך num לא נמצא במערך mat, יוחזר false ולא יודפס כלום.

לדוגמה, אם mat הוא המערך המוצג לעיל, ו-num = 22 יוחזר הערך true ויודפסו השורות הבאות:

row = 2
col = 3

אם mat הוא המערך המוצג לעיל, ו-num = 23 יוחזר הערך false ולא יודפס כלום.

השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.

mat =
[[1, 3, 7, 9],
 [6, 4, 15, 11],
 [36, 50, 21, 22],
 [60, 55, 30, 26]],
num = 15

row = 1
col = 2
true

mat =
[[1, 3, 7, 9],
 [6, 4, 15, 11],
 [36, 50, 21, 22],
 [60, 55, 30, 26]],
num = 100

false

mat =
[[1, 2],
 [4, 3]],
num = 3

true

mat =
[[1, 3, 7, 9],
 [6, 4, 15, 11],
 [36, 50, 21, 22],
 [60, 55, 30, 26]],
num = 6

row = 1
col = 0
true