חיפוש

עזרה

הרשמה

התחברות

עדכונים

מדעי המחשב
UnderWarrior Forums : מדעי המחשב

נושא: שאלה במבנה נתונים

כותב

הודעה

<< נושא קודם | נושא הבא >>

קרן
אורח

הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647

נשלח בתאריך: 27 June 2008 בשעה 12:38

| IP רשוּם

1) Given a sorted array A of n positive integers followed by n zeros

A={a1,a2,....,an, 0,0,...0}

פעמים n 0מופיע

Given that n is not known in advance (i.e. the size of A is also unknown – so you can't jump to the last cell or to compute n/2, ext…), describe an O(logn) time algorithm that finds the index of a positive integer x in A, if x is in A.

חזרה לתחילת העמוד

shoshan
מנהל האתר

הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637

נשלח בתאריך: 27 June 2008 בשעה 14:35

| IP רשוּם

בואי לצורך פישוט נניח ש"גדול מ" מחזיר אמת עבור 0 ומספר טבעי (כלומר 0 גדול מכל מספר טבעי)

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

__________________
עד מתי רשעים יעלוזו?

עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.

חזרה לתחילת העמוד

קרן
אורח

הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647

נשלח בתאריך: 27 June 2008 בשעה 15:06

| IP רשוּם

תודה רבה רבה

חזרה לתחילת העמוד

אם ברצונך להגיב לנושא זה עליך קודם להתחבר
אם אינך רשום/ה כבר עליך להרשם

גרסת הדפסה

אינך יכול/ה לשלוח נושאים חדשים בפורום זה
אינך יכול/ה להגיב לנושאים בפורום זה
אינך יכול/ה למחוק את הודעותיך ותגוביך בפורום זה
אינך יכול/ה לערוך את הודעותיך ותגובותיך בפורום זה
אינך יכול/ה לצור סקרים בפורום זה
אינך יכול/ה להצביע בסקרים בפורום זה