Search a 2D Matrix
נתונה לך רשת של מספרים שלמים matrix עם m שורות ו-n עמודות, ומספר שלם target. כל שורה ממוינת בסדר עולה, והערך הראשון בכל שורה גדול מהערך האחרון בשורה שמעליה. החזר true אם target מופיע ברשת, ו-false אחרת, בזמן O(log(m × n)).
פונקציה
- matrixinteger-2d-array
- הרשת, הנתונה כרשימה של שורות, ממוינת שורה אחר שורה
- targetinteger
- הערך שיש לחפש
- מחזירהboolean
- true אם היעד נמצא ברשת, false אחרת
אילוצים
1 ≤ m, n ≤ 100, כאשרm = matrix.lengthו-n = matrix[i].length- לכל שורה יש אותו אורך
n. -104 ≤ matrix[i][j], target ≤ 104- כל שורה ממוינת בסדר עולה ממש, והערך הראשון בכל שורה גדול מהערך האחרון בשורה הקודמת.
דוגמאות
- קלט
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 26
- פלט
- true
- הסבר
- קראו שורה אחר שורה: 12 הערכים הם רשימה ממוינת אחת. חיפוש בינארי במיקומים 0 עד 11 בודק את 21 במיקום 5 (קטן מדי), את 33 במיקום 8 (גדול מדי), ואז מוצא את 26 במיקום 6.
- קלט
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 16
- פלט
- false
- הסבר
- 16 היה מופיע אחרי 14, הערך האחרון בשורה 0, ולפני 17, הערך הראשון בשורה 1. אין שום דבר ביניהם, לכן 16 לא נמצא ברשת.
שאלת המשך
נניח שלשורות יכול להיות אורך שונה, אך הן עדיין ממוינות ברצף. איך היית ממיר מיקום לשורה ולעמודה, ומה תהיה עלות החיפוש?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
קרא את המטריצה שורה אחר שורה, משמאל לימין, כאילו הייתה רשימה ארוכה אחת. מה אתה מבחין לגבי הסדר של הערכים ברשימה הזאת?
שני הכללים יחד פירושם שהמטריצה כולה, כשקוראים אותה שורה אחר שורה, היא רשימה ממוינת אחת של
m × nערכים. אפשר לבצע בה חיפוש בינארי בלי ליצור אותה כלל.חיפוש בינארי על פני המיקומים
0עדm × n - 1. המיקוםpנמצא בשורהp / nובעמודהp % n(חלוקה שלמה), כך שבכל צעד קוראים תא אחד ומוותרים על מחצית מהמיקומים שנותרו.
פתרון
שני כללי הסדר יחד הופכים את הרשת, בקריאה שורה אחר שורה, לרשימה ממוינת אחת של m × n ערכים. בצעו חיפוש בינארי ברשימה לפי מיקום, והמירו כל מיקום בחזרה לשורה ולעמודה באמצעות חילוק אחד. רשת של 100 על 100 דורשת אז לכל היותר 14 השוואות במקום 10000.
בדוק כל תא
האינטואיציה
השווה כל תא ל־target והחזר true במקרה של התאמה, false אחרי התא האחרון. הפונקציה קוראת כל תא, ולכן היא נכונה לכל רשת, ממוינת או לא. היא אף פעם לא מנצלת את הסדר, ולכן רשת בגודל 100 על 100 דורשת עד 10000 השוואות.
אלגוריתם
- עבור כל שורה של
matrix, בדקו כל ערך לפי הסדר. - אם הערך שווה ל־
target, החזירוtrue. - אחרי הלולאות, החזירו
false.
def searchMatrix(matrix, target):
for row in matrix:
for value in row:
if value == target:
return True
return Falseלכו מהפינה הימנית העליונה
האינטואיציה
מהתא הימני העליון, כל ערך משמאל קטן יותר וכל ערך מתחתיו גדול יותר. אם התא גדול מ־target, גם העמודה שמתחתיו גדולה יותר: זוז שמאלה והסר את העמודה הזאת. אם הוא קטן יותר, גם השורה שמשמאלו קטנה יותר: זוז למטה והסר את השורה הזאת.
בדוגמה הראשונה, 14 קטן מ־26, לכן זוז למטה אל 30. 30 גדול יותר, לכן זוז שמאלה אל 26, והתאמה. כל צעד מסיר שורה או עמודה, לכן נדרשים לכל היותר m + n צעדים: 200 ברשת בגודל 100 על 100. הסריקה זקוקה רק לכך שהשורות והעמודות יהיו ממוינות, ולכן היא מתעלמת ממחצית מהמידע שהרשת הזאת מספקת.
אלגוריתם
- התחל בשורה
0ובעמודה האחרונה. - כל עוד השורה והעמודה נמצאות בתוך הרשת, קרא את התא.
- אם הוא שווה ל־target, החזר
true. - אם הוא גדול יותר, זוז עמודה אחת שמאלה; אם הוא קטן יותר, זוז שורה אחת למטה.
- כשתצא מהרשת, החזר
false.
def searchMatrix(matrix, target):
# Start at the top-right corner: left is smaller, down is larger.
r, c = 0, len(matrix[0]) - 1
while r < len(matrix) and c >= 0:
value = matrix[r][c]
if value == target:
return True
if value > target:
c -= 1 # every value below in this column is larger still
else:
r += 1 # every value to the left in this row is smaller still
return Falseחיפוש בינארי ברשת השטוחה
האינטואיציה
מספרים את התאים לפי שורות: בשורה 0 נמצאים המיקומים 0 עד n - 1, בשורה 1 נמצאים n עד 2n - 1, וכן הלאה. כל שורה ממוינת ומתחילה מעל המקום שבו הסתיימה השורה הקודמת, לכן הערכים רק עולים ככל שהמיקום מתקדם. זו רשימה ממוינת, ואפשר להשתמש בחיפוש בינארי.
אין צורך לבנות את הרשימה. מיקום p נמצא בשורה p / n ובעמודה p % n, באמצעות חלוקה שלמה. בדוגמה הראשונה n = 4, לכן מיקום 6 נמצא בשורה 1, בעמודה 2, ובה נמצא הערך 26. כל השוואה מחלקת לשניים את מספר המיקומים שבהם target עשוי להימצא: לכל היותר 14 השוואות עבור 10000 תאים, תוך שימוש בשני אינדקסים של זיכרון נוסף.
אלגוריתם
- יהיו
mו-nמספר השורות והעמודות, והגדרlo = 0,hi = m × n - 1. - כל עוד
lo ≤ hi, קח אתmidשבאמצע ביניהם. - קרא את
value = matrix[mid / n][mid % n]. - אם
valueשווה ל-target, החזרtrue. אם הוא קטן יותר, הגדרlo = mid + 1; אחרת הגדרhi = mid - 1. - כשהלולאה מסתיימת, החזר
false.
def searchMatrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
# Read row by row, the cells form one sorted list of rows * cols values.
# Position p of that list is matrix[p // cols][p % cols].
lo, hi = 0, rows * cols - 1
while lo <= hi:
mid = (lo + hi) // 2
value = matrix[mid // cols][mid % cols]
if value == target:
return True
if value < target:
lo = mid + 1
else:
hi = mid - 1
return False
מלכודות ומקרי קצה
- חלוקה במספר השורות במקום במספר העמודות. המיקום
pנמצא בשורהp / n; החלפתו ב־mגורמת לכך שהקוד מצליח ברשתות ריבועיות ונכשל ברשתות עם 3 שורות ו־4 עמודות. - בגרסה עם שני חיפושים, אי־טיפול במקרה שבו
targetקטן מ־matrix[0][0]. אף שורה לא מתחילה בערך השווה לו או קטן ממנו, ואינדקס שורה של-1מגיע לחיפוש השני. - שימוש בתנאי הלולאה
lo < hiעםhiכולל. רשת בגודל 1 על 1 שמכילה אתtargetמחזירהfalse, כי הלולאה כלל לא מתבצעת. - ב־Lua וב־R, שכחת ההיסט לאינדקסים שמתחילים ב־1: המיקום
pנמצא בשורהp / n + 1ובעמודהp % n + 1.
שאלות נפוצות3
מהי סיבוכיות הזמן של חיפוש במטריצה דו־ממדית?
חיפוש בינארי במערך השטוח מתבצע בזמן O(log(m × n)) ובמקום O(1): לכל היותר 14 השוואות עבור 10000 תאים. מכיוון ש־log(m × n) = log m + log n, הוא שקול לחיפוש אחר השורה ואז בתוכה.
האם להשתמש בהליכה לפינה הימנית העליונה או בחיפוש בינארי?
ההליכה בפינות אורכת O(m + n) צעדים, ודורשת רק שהשורות והעמודות יהיו ממוינות, ולכן היא פותרת גם את הגרסה שבה שורה עשויה להתחיל מתחת לנקודה שבה מסתיימת השורה שמעליה. כאשר כל שורה מתחילה מעל המקום שבו הסתיימה השורה הקודמת, כמו כאן, חיפוש בינארי מהיר יותר.
האם גם שני חיפושים בינאריים, אחד עבור השורה ואחד בתוכה, הם נכונים?
כן. בצע חיפוש בינארי בעמודה הראשונה כדי למצוא את השורה האחרונה שהערך הראשון בה קטן או שווה ל-target, ואז בצע חיפוש בינארי בשורה הזאת. זמן הריצה הוא O(log m + log n), אותו חסם. החיפוש היחיד מבצע את אותה העבודה עם לולאה אחת ופחות מקרי קצה.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def searchMatrix(matrix, target):
# כתבו כאן קודבדיקה #1
בדיקה #2
ארגומנטים
matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]] target = 26
הפלט הצפוי
true