עוד שאלה טריקית במבוא למבני נתונים ואלג'

[uvdude]

עוד שאלה טריקית במבוא למבני נתונים ואלג'

נתון מערך ממויין A של n מספרים שלמים, לא בהכרח שונים. נתונים שני שלמים x,y כאשר x < y. כתוב אלגוריתם הבודק אם מתקיימים: - מספר המופעים של x שווה למספר המופעים של y. - קיים לכל היותר ערך אחד m המקיים x < m < y. זמן ריצה נדרש: O(lgn). אין לי מושג אפילו מאיפה להתחיל

אי אפשר לעשות חיפוש בינארי ולהשוות איבר איבר, זה יביא אותנו לO... יש הצעות

 

[Maha Vailo]

מה הבעיה עם החיפוש הבינארי?

אפשר לעשות חיפוש בינארי כדי למצוא למשל את האינדקס הראשון בו מופיע X. נניח שהמערך מסודר כך שהמספרים הנמוכים יותר נמצאים בצד שמאל, אז עושים חיפוש רגיל, רק שאם מוצאים X בתא נתון בוחרים את החלק השמאלי יותר של המערך וממשיכים שם. בסוף שמגיעים לאיבר אחד, אז או שהוא X ואז זה האיבר הראשון או שהוא מצד שמאל של X, כלומר ב log n אפשר למצוא את האינדקס הראשון בו מופיע X. בצורה דומה מוצאים את האיבר האחרון של X ואת הראשון והאחרון של Y. אחר כך נותר לבדוק אם בין X לY יש לכל היותר ערך יחיד וזה רק אם משמאל לY השמאלי ביותר יש X או יש M והוא שווה למספר שמימין לX הימני. אלה ארבעה חיפושים של log n ולכן פותר את הבעיה.

 

[uvdude]

אכן. תודה!