Find First and Last Position of Element in Sorted Array
מקבלים רשימה של מספרים שלמים nums הממוינת בסדר לא יורד, כך שערך יכול להופיע יותר מפעם אחת, ומספר שלם target. החזירו רשימה של שני אינדקסים, כאשר הספירה מתחילה מ־0: המיקום הראשון והאחרון שבהם target מופיע. אם target לא נמצא ברשימה, החזירו [-1, -1]. שאפו לזמן ריצה של O(log n).
פונקציה
- numsinteger-array
- הרשימה הממוינת של מספרים שלמים, שבה עשויים להופיע ערכים חוזרים
- targetinteger
- הערך שיש לחפש
- מחזירהinteger-array
- האינדקס הראשון והאחרון של target, או [-1, -1] אם הוא חסר
אילוצים
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104numsמסודר בסדר לא יורד.
דוגמאות
- קלט
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 5
- פלט
- [1, 3]
- הסבר
- שלושת העותקים של 5 נמצאים באינדקסים 1, 2 ו־3, לכן הרצף מתחיל ב־1 ומסתיים ב־3. באינדקס 0 נמצא 3 ובאינדקס 4 נמצא 8, לכן הרצף אינו יכול להימשך מעבר לכך.
- קלט
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 7
- פלט
- [-1, -1]
- הסבר
- 7 היה ממוקם בין 5 באינדקס 3 לבין 8 באינדקס 4, ואף אחד מהם אינו 7. הרשימה אינה מכילה עותק, ולכן התשובה היא
[-1, -1].
שאלת המשך
אם אותה רשימה מקבלת אלפי שאילתות עבור יעדים שונים, האם מעבר אחד עליה מראש יכול להפוך כל שאילתה למהירה יותר מ־O(log n)?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
מכיוון ש-
numsממוינת, כל העותקים שלtargetנמצאים זה לצד זה ברצף אחד. צריך למצוא את שני הקצוות של הרצף הזה.מציאת עותק אחד והתקדמות החוצה ממנו עלולות לעלות
O(n)כשהרצף ארוך. במקום זאת, שנו את החיפוש הבינארי כך שימשיך שמאלה אחרי מציאת התאמה: כך הוא נעצר באינדקס הראשון שהערך בו גדול או שווה למספר שאתם מחפשים.כתבו פונקציית עזר שמחזירה את האינדקס הראשון שבו
nums[i] ≥ value. קראו לה עםtargetכדי לקבל את תחילת הרצף, בדקו שהערך שם הואtarget, וקראו לה עםtarget + 1: הרצף מסתיים אינדקס אחד לפני כן.
פתרון
חיפוש בינארי רגיל נעצר בעותק הראשון של target שהוא פוגש, והעותק הזה יכול להימצא בכל מקום ברצף. במקום זאת, חפשו את הגבול התחתון: האינדקס הראשון שהערך בו גדול או שווה למספר נתון. הגבולות התחתונים של target ושל target + 1 נותנים את שני קצות הרצף בזמן O(log n).
סרוק את הרשימה כולה
האינטואיציה
עוברים על הרשימה פעם אחת. האינדקס הראשון שמכיל את target הוא ההתחלה, והאחרון הוא הסוף. אם target לא מופיע אף פעם, שניהם נשארים -1.
השיטה עובדת על כל רשימה, ממוינת או לא, וזו גם חולשתה: היא קוראת את כל n הערכים. רשימה של 10^4 ערכים דורשת 10,000 השוואות, בעוד שכ־28 היו מספיקות.
אלגוריתם
- הגדר את
first = last = -1. - עבור כל אינדקס
i, אםnums[i]שווה ל-target, הגדר אתfirst = iכאשרfirstעדיין-1, והגדר אתlast = i. - החזר את
[first, last].
def searchRange(nums, target):
first = last = -1
for i, value in enumerate(nums):
if value == target:
if first == -1:
first = i # the first match fixes the start
last = i # every later match moves the end
return [first, last]מצא עותק אחד, ואז הרחב
האינטואיציה
חפש בינארית אינדקס כלשהו שמכיל את target. הרשימה ממוינת, לכן כל העותקים נמצאים ברצף רציף סביב אותו אינדקס: התקדם שמאלה וימינה כל עוד השכן עדיין שווה ל־target.
החיפוש עולה O(log n), והמעבר עולה צעד אחד לכל עותק, k בסך הכול. כאשר רוב הרשימה מכילה את target, נניח 10^4 עותקים, המעבר קורא כל ערך, וחוזרים לסריקה ליניארית.
אלגוריתם
- בצע חיפוש בינארי כדי למצוא אינדקס כלשהו
foundשעבורוnums[found] == target. - אם אין כזה, החזר
[-1, -1]. - הזז את
firstשמאלה מ־foundכל עוד הערך שלפניו שווה ל־target. - הזז את
lastימינה מ־foundכל עוד הערך שאחריו שווה ל־target. - החזר
[first, last].
def searchRange(nums, target):
# An ordinary binary search finds some copy of target, if there is one.
lo, hi = 0, len(nums) - 1
found = -1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
found = mid
break
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
if found == -1:
return [-1, -1]
# The copies sit next to each other, so walk out to both ends of the run.
first = last = found
while first > 0 and nums[first - 1] == target:
first -= 1
while last < len(nums) - 1 and nums[last + 1] == target:
last += 1
return [first, last]שני חיפושים בינאריים למציאת הגבול התחתון
האינטואיציה
נשאל שאלה אחרת: מהו האינדקס הראשון שהערך בו גדול או שווה ל־value? האינדקס הזה הוא החסם התחתון, או n אם אין ערך מתאים. נשמור על טווח חצי פתוח [lo, hi) שתמיד מכיל אותו. אם nums[mid] < value, אז mid וכל מה שלפניו קטנים מדי. אחרת, mid מתאים, אבל ייתכן שגם אינדקס מוקדם יותר מתאים, ולכן mid נשאר בטווח בתור hi החדש. הלולאה לעולם אינה נעצרת מוקדם כשנמצא ערך מתאים.
החסם התחתון של target הוא המקום שבו הרצף שלו מתחיל. הערכים הם מספרים שלמים, לכן הערך הראשון שגדול מ־target נמצא בחסם התחתון של target + 1, והרצף מסתיים אינדקס אחד לפניו. בדוגמה הראשונה, החסם התחתון של 5 הוא 1, והחסם התחתון של 6 הוא 4, במקום שבו נמצא 8: הרצף הוא [1, 3]. שני החיפושים אורכים בערך 28 צעדים עבור 10^4 ערכים, בלי קשר לאורך הרצף.
אלגוריתם
- כתבו
lowerBound(value): התחילו עםlo = 0,hi = n; כל עודlo < hi, אםnums[mid] < valueהגדירוlo = mid + 1, אחרת הגדירוhi = mid; החזירו אתlo. - הגדירו
first = lowerBound(target). - אם
first == nאוnums[first] != target, החזירו[-1, -1]. - הגדירו
last = lowerBound(target + 1) - 1והחזירו[first, last].
def lowerBound(nums, value):
# The first index whose number is at least value, or len(nums) if none is.
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < value:
lo = mid + 1 # nums[mid] and everything before it is too small
else:
hi = mid # nums[mid] qualifies, but an earlier index might too
return lo
def searchRange(nums, target):
first = lowerBound(nums, target)
if first == len(nums) or nums[first] != target:
return [-1, -1]
# The run of target ends right before the first number above target.
last = lowerBound(nums, target + 1) - 1
return [first, last]
מלכודות ומקרי קצה
- החזרה של התוצאה מיד כשמתקיים
nums[mid] == target. האינדקס הזה יכול להיות בכל מקום ברצף: ב־[3, 5, 5, 5, 8]האמצע הראשון הוא באינדקס 2, שאינו אחד הקצוות. - כתיבת
hi = mid - 1בחיפוש הגבול התחתון כאשרnums[mid] ≥ value. כך מושלךmid, שעשוי להיות התשובה. - קריאת
nums[first]בלי לבדוקfirst < n. כשהערך שלtargetגדול מכל הערכים, כמו 13 בדוגמאות, הגבול התחתון הואn, מיקום אחד אחרי הסוף. - שכחת ההזזה ב־Lua וב־R. הרשימות שלהן מתחילות ב־1, לכן יש להפחית 1 משני המיקומים.
שאלות נפוצות3
מהי סיבוכיות הזמן של מציאת המיקום הראשון והאחרון?
זמן O(log n) ומקום O(1), באמצעות שני חיפושים בינאריים. אף אחד מהם לא נעצר כשנמצא התאמה, ולכן העלות אינה תלויה במספר העותקים של ערך היעד: כ־14 צעדים לכל חיפוש עבור 10^4 ערכים.
מהו חסם תחתון בחיפוש בינארי?
הגבול התחתון של ערך הוא האינדקס הראשון שהאיבר בו גדול מערך זה או שווה לו, או אורך הרשימה אם אין כזה. זהו המקום שבו הערך יוכנס כדי לשמור על הרשימה ממוינת. הגבול העליון הוא האינדקס הראשון שהאיבר בו גדול ממש.
האם פונקציית חיפוש בינארי אחת יכולה למצוא גם את האינדקס הראשון וגם את האחרון?
כן. הוסיפו לחיפוש דגל: בהתאמה, תעדו את האינדקס והמשיכו לחפש שמאלה כדי למצוא את ההופעה הראשונה, או ימינה כדי למצוא את האחרונה. גם קריאה לחיפוש חסם תחתון עבור target ועבור target + 1 עובדת. שניהם פועלים ב־O(log n).
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def searchRange(nums, target):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
ארגומנטים
nums = [3, 5, 5, 5, 8, 9, 9, 12] target = 5
הפלט הצפוי
[1, 3]