נתון מערך בן n מספרים שלמים. ידוע שהוא מכיל את הערך 10 k פעמים. ידוע גם שכל ה10-ים מרוכזים בסוף המערך. האם ניתן לחשב את k
ב(O(logk? ענה בכן ולא
אין תשובה בפתרון שניתן. האם זה כן או לא?
שאלה 1ד מבחן סמסטר ג 2009
מנהל: TA_Isana
Re: שאלה 1ד מבחן סמסטר ג 2009
כן
קודם כל נמצא באיזה תחום לחפש
הלולאה בזמן הדרוש ועכשיו נותר רק לחפש במערך בגודל 2k מה שגם עומד בזמן הדרוש
קודם כל נמצא באיזה תחום לחפש
קוד: בחירת הכל
i=0
len=A.length
while(A[len-2^i]=10){
i=i+1
} // now 2^i >= k >= 2^(i-1)