שאלה על מציאת חציון במערכים ממויינים

[white shadow 3]

שאלה על מציאת חציון במערכים ממויינים

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

יש לי 2 מערכים, כל אחד מהם מכיל n איברים (כל 2n האיברים שונים זה מזה)
המטרה: מציאת החציון של מיזוג של המערכים בזמן O(log).

אשמח לרעיונות
תודה!

 

[עעעערררר]

ובכן

חציון של מערך ממויין, הוא האיבר האמצעי בו, ולכן ניתן למציאה בזמן קבוע.
בנוסף, אם משמיטים מאוסף כמות זוגית של איברים, שחציים קטנים מהחציון וחלקם גדולים מהחציון, לא משנים את החציון.
&nbsp
נשווה את החציונים של שני המערכים. בה"כ, החציון של B גדול משל A.
אזי ברור שהחציון של המיזוג הוא בין החציונים של המערכים (למה?)
לפיכך, איברי החצי הראשון של A קטנים מהחציון, ואיברי החצי השני של B גדולים מהחציון.
לכן, מספיק למצוא את החציון של מיזוג החצי השני של A עם החצי הראשון של B.

 

[white shadow 3]

בוקר טוב.

איך ניתן למצוא חציון של מיזוג של החצאים בזמן Log?
&nbsp

 

[white shadow 3]

אוקי נראה לי שהבנתי...

אז בגדול
בעצם אני כל פעם זורק מכל מערך מספר שווה של איברים (עבור מערך אחד - איברים מימין לחציון ועבור השני איברים משמאךל לחציון) וחוזר על הפעולה הזאת הזאת (מציאת חציון לכל מערך בנפרד-->השוואת חציונים--<זריקת איברים) עד שבסוף אני מגיע ל-2 מערכים ששניהם גודל 1 או שאחד מהם מגודל אחד והשני גודל 2 (יווצר מצב שאני לא יכול לזרוק מאף אחד מהם איברים)
&nbsp
שאלה קטנה נוספת - איך אני מוכיח / מסביר פורמלית שהחציון באמת ימצא בטווח שבין החציונים של שני המערכים?
&nbsp
תודה!!

 

[עעעערררר]

רמז

אם רוב איברי קבוצה גדולים מאיבר מסויים, אז החציון גדול מהאיבר הזה.

 

[פרסאוס]

N נתון? המערכים ממויינים?

 

[white shadow 3]

n לא נתון. כל מערך בפני עצמו הוא נתון כממויין

 

[פרסאוס]

אם לא נתון האורך איך ניתן

לדעת אם הגעת לסוף המערך?

 

[white shadow 3]

אני מניח שכוונת המשורר הייתה

שכל מערך הוא בגודל n אז האיבר האחרון שלו זה A(n-1) (נניח מתחילים מ-0)
&nbsp
אגב, רק אציין כי השאלה ששאלתי (שלקוחה ממבחן כלשהוא שראיתי אתמול) הייתה מנוסחת בדיוק כמו שכתבתי בהודעה המקורית

 

[פרסאוס]

זה לא משנה.

אם אתה לא יודע מהו N לא תוכל להגיע ל n-1

 

[white shadow 3]

חשבתי אולי בכיוון של שימוש בערימות אבל

למיטב ידיעתי רק הבניה של הערימה מתוך המערך לוקחת לי O וזה כבר חורג מהתנאים

 

[nocgod]

חיפוש קצרצר בגוגל מוצא לך פיתרון לתרגיל עם הסבר

http://www.geeksforgeeks.org/median-of-two-sorted-arrays/