חיפוש במערך חלקלק

נתון מערך חד-ממדי arr ובו מספרים שלמים.

נגדיר: מערך חלקלק (slippery) הוא מערך שבו ההפרש בין כל שני איברים צמודים הוא לכל היותר 1.

הנה דוגמה למערך חלקלק:

arr = {3, 4, 5, 6, 6, 6, 7, 6, 5, 6, 5, 6, 5, 6, 7, 8, 7, 6, 7, 8, 8, 9, 9, 9, 8, 9, 8}

כתבו את השיטה:

slipperyArraySearch1 המקבלת שני איברים, אחד מהמערך a והשני מהמערך b כך שההפרש (בערך מוחלט) בין שני האיברים האלו הוא הקטן ביותר מבין כל זוגות ההפרשים האפשריים. יש להחזיר את ההפרש ולהדפיס את זוג האיברים.

אפשר להניח שהערך במקום האחרון במערך גדול ממש מהערך במקום הראשון במערך. כתבו שיטה סטטית יעילה ככל האפשר המקבלת מערך חלקלק arr ומספר שלם x שמובטח שהוא גדול או שווה לאיבר הראשון במערך, וקטן או שווה לאיבר האחרון במערך. על השיטה להחזיר את המיקום במערך arr שבו נמצא x. אם הוא לא נמצא, על השיטה להחזיר את הערך -1. אם המספר x מופיע יותר מפעם אחת במערך arr, השיטה צריכה להחזיר אחד מהאינדקסים שבהם המספר מופיע. לא משנה איזה.

לדוגמה, בהינתן המערך arr שכתוב לעיל:

• אם x=3, השיטה תחזיר 0.
• אם x=4, השיטה תחזיר 1.
• אם x=5, השיטה תחזיר אחד מהערכים הבאים: 12, 10, 8, 2 (לא משנה איזה).
• הערך x=9 לא יכול להיות ערכו של x, כי מובטח שהשיטה לא תיקרא עם ערך x שהוא קטן מ-3 או גדול מ-8 (הערכים שבקצות המערך). אבל שימו לב שערכים כאלה (כמו 9) כן יכולים להיות איברים בתוך המערך.

הנה תיאור מתמטי של ההנחות שניתן להניח:

• |arr[i] - arr[i+1]| <= 1 for every 0 <= i < arr.length - 1
• arr[0] < arr[arr.length - 1] and arr[0] <= x <= arr[arr.length - 1]

כתבו את השיטה:

slipperyArraySearch2 המקבלת מערך חלקלק arr ומספר שלם x. על השיטה להחזיר את המיקום במערך arr שבו נמצא x. אם הוא לא נמצא, על השיטה להחזיר את הערך -1. אם המספר x מופיע יותר מפעם אחת במערך arr, השיטה צריכה להחזיר אחד מהאינדקסים שבהם המספר מופיע. לא משנה איזה.

שימו לב: ההבדל בין שני הסעיפים הוא שבסעיף א מובטח שהערך שמחפשים גדול או שווה לאיבר הראשון במערך וקטן או שווה לאיבר האחרון במערך. בסעיף ב לא מובטח דבר לגבי הערך שמחפשים.

השיטות צריכות להיות יעילות ככל האפשר, גם מבחינת סיבוכיות הזמן וגם סיבוכיות המקום צריכה להיות קבועה , O(1).

arr = [3, 4, 5, 6, 6, 6, 7, 6, 5, 6, 5, 6, 5, 6, 7, 8, 7, 6, 7, 8, 8, 9, 9, 9, 8, 9, 8],
x = 3

OK
OK

arr = [3, 4, 5, 6, 6, 6, 7, 6, 5, 6, 5, 6, 5, 6, 7, 8, 7, 6, 7, 8, 8, 9, 9, 9, 8, 9, 8],
x = 4

OK
OK

arr = [3, 4, 5, 6, 6, 6, 7, 6, 5, 6, 5, 6, 5, 6, 7, 8, 7, 6, 7, 8, 8, 9, 9, 9, 8, 9, 8],
x = 5

OK
OK

arr = [3, 4, 5, 6, 6, 6, 7, 6, 5, 6, 5, 6, 5, 6, 7, 8, 7, 6, 7, 8, 8, 9, 9, 9, 8, 9, 8],
x = 8

OK
OK

arr = [3, 4, 5, 6, 6, 6, 7, 6, 5, 6, 5, 6, 5, 6, 7, 8, 7, 6, 7, 8, 8, 9, 9, 9, 8, 9, 8],
x = 9

N/A
OK

arr = [3, 4, 5, 6, 6, 6, 7, 6, 5, 6, 5, 6, 5, 6, 7, 8, 7, 6, 7, 8, 8, 9, 9, 9, 8, 9, 8],
x = 2

N/A
-1

arr = [3, 4, 5, 6, 6, 6, 7, 6, 5, 6, 5, 6, 5, 6, 7, 8, 7, 6, 7, 8, 8, 9, 9, 9, 8, 9, 8],
x = 10

N/A
-1

arr = [9, 8, 8, 7, 6, 5, 5, 4],
x = 6

N/A
OK

arr = [-3, -2, -3, -2, -1, 0, -1, 0, 1],
x = -1

OK
OK

arr = [1, 2, 3, 4, 5],
x = 3

OK
OK

arr = [5, 5, 5, 6],
x = 6

OK
OK

arr = [5],
x = 7

N/A
-1