שאלה 1ד מבחן סמסטר ג 2009

[zoran]

נתון מערך בן n מספרים שלמים. ידוע שהוא מכיל את הערך 10 k פעמים. ידוע גם שכל ה10-ים מרוכזים בסוף המערך. האם ניתן לחשב את k
ב(O(logk? ענה בכן ולא
אין תשובה בפתרון שניתן. האם זה כן או לא?

[TA_Yakim]

כן
קודם כל נמצא באיזה תחום לחפש

קוד: בחירת הכל

i=0
len=A.length
while(A[len-2^i]=10){ 
                                i=i+1
}   // now 2^i >= k >= 2^(i-1)

הלולאה בזמן הדרוש ועכשיו נותר רק לחפש במערך בגודל 2k מה שגם עומד בזמן הדרוש