חיפוש במערך סכומים

• נתון מערך חד-ממדי a המכיל מספרים שלמים ממוין בסדר לא יורד. נגדיר את מערך הסכומים שלו b כך:

• התא הראשון של המערך b מכיל את הערך של התא הראשון במערך a. כלומר: b[0]=a[0]

• לכל i החל מ-1 ועד לתא האחרון במערך b, התא ה-i מכיל את סכום התאים a[0] עד a[i].

כלומר, b[i] = a[0]+a[1]+...+a[i]

לדוגמה, עבור המערך הבא:

int[] a = {0, 2, 3, 4, 5}

מערך הסכומים יהיה:

int[] b = {0, 2, 5, 9, 14}

 

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

• get המקבלת כפרמטרים מערך סכומים b ואינדקס k ומחזירה את a[k].

 

• find המקבלת כפרמטרים מערך סכומים b (שהתקבל מהמערך a), וערך שלם x, ומחזירה את האינדקס במערך a שמכיל את הערך x. כלומר, השיטה תחזיר k אם a[k] == x, ואם הערך x לא קיים במערך a השיטה תחזיר -1.

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

b = [0, 2, 5, 9, 14],
x = 5

4

b = [1, 3],
x = 2

1

b = [3, 8, 15],
x = 3

0

b = [-2, -2, 2, 11],
x = 4

2

b = [0, 2, 5, 9, 14],
x = 1

-1

b = [1, 4, 10, 20, 35, 56],
x = 9

-1

b = [5, 17, 37, 70, 120],
x = 5

0

b = [2, 5, 9, 15],
x = 4

2