שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - האוניברסיטה הפתוחה 2026 - חיפוש בינארי

מערך נקרא "ממוין מסובב" (Rotated Sorted Array) אם הוא מתקבל ממערך ממוין (עולה ממש) שעבר הזזה ציקלית (סיבובים) ימינה מספר פעמים. כלומר, לקחו מערך ממוין, חתכו את הסוף שלו והדביקו אותו להתחלה. לדוגמה, המערך הבא הוא ממוין מסובב: $[15, 20, 25, 1, 5, 8, 10]$ (המערך המקורי היה: $[1, 5, 8, 10, 15, 20, 25]$ ועבר הזזה). שימו לב: גם מערך ממוין רגיל נחשב למערך מסובב (עם הזזה של 0). הניחו כי כל איברי המערך שונים זה מזה. א. (10 נק') כתבו אלגוריתם המוצא את האינדקס של האיבר המינימלי במערך (בדוגמה לעיל: האינדקס של 1). זמן הריצה הנדרש הוא לוגריתמי: $O(\log n)$. הסבירו בקצרה את נכונות האלגוריתם. ב. (8 נק') כתבו אלגוריתם המקבל מערך ממוין מסובב ומספר כלשהו: $x$. האלגוריתם יחזיר את האינדקס של $x$ במערך (או יחזיר "לא קיים"). זמן הריצה הנדרש הוא לוגריתמי: $O(\log n)$. הסבירו בקצרה את נכונות האלגוריתם. ג. (7 נק') נניח כעת שאיברי המערך אינם בהכרח שונים (ייתכנו כפילויות), והמערך עדיין ממוין-מסובב. הראו שקיים קלט שעבורו האלגוריתם שכתבתם למציאת האיבר המינימלי יחזיר תשובה שגויה.

רמז: התכונה המרכזית של מערך ממוין-מסובב היא שבכל חלוקה שלו לשניים, לפחות אחד מהחצאים יהיה ממוין כסדרו. ניתן לנצל תכונה זו כדי ליישם גרסאות של חיפוש בינארי.

פתרון: ### סעיף א: מציאת האיבר המינימלי האלגוריתם מבוסס על **חיפוש בינארי**. הרעיון המרכזי הוא שבכל שלב נצמצם את טווח החיפוש `[low..high]` בחצי, על ידי השוואת האיבר האמצעי, `A[mid]`, לאיבר בקצה הטווח, `A[high]`. מכיוון שהמערך הוא תוצאה של סיבוב מערך ממוין, תמיד יהיה קיים "שבר" או "קפיצה" בנקודה אחת, והאיבר המינימלי יהיה מיד אחרי אותה נקודה. ההשוואה בין `A[mid]` ל-`A[high]` מאפשרת לנו לזהות באיזה צד של `mid` נמצא השבר. **תיאור האלגוריתם:** נאתחל שני מצביעים, `low = 0` ו-`high = n-1`. כל עוד `low < high`: 1. נחשב את האינדקס האמצעי: `mid = floor((low + high) / 2)`. 2. נשווה את `A[mid]` עם `A[high]`: - אם `A[mid] > A[high]`: הדבר מעיד על כך שהחלק `A[low..mid]` הוא רציף, ממוין וערכיו גבוהים יותר מהערכים שבתחילת המערך הממוין המקורי (שנמצאים כעת באזור `A[high]`). לכן, נקודת השבר והאיבר המינימלי חייבים להימצא מימין ל-`mid`. נקדם את הגבול התחתון: `low = mid + 1`. - אם `A[mid] <= A[high]`: הדבר מעיד על כך שהחלק `A[mid..high]` הוא רציף וממוין. במצב זה, האיבר המינימלי יכול להיות `A[mid]` עצמו, או איבר כלשהו הנמצא משמאלו. בכל מקרה, האיבר המינימלי אינו נמצא מימין ל-`mid`. לכן, נצמצם את טווח החיפוש לחלק השמאלי (כולל `mid`): `high = mid`. הלולאה מסתיימת כאשר `low == high`, ואינדקס זה הוא האינדקס של האיבר המינימלי. **נכונות וסיבוכיות:** **שמורת הלולאה** של האלגוריתם היא שהאיבר המינימלי נמצא תמיד בטווח `A[low..high]`. בכל איטרציה, האלגוריתם מסיר חלק מהמערך שבו מובטח שהמינימום אינו נמצא. מכיוון שבכל שלב אנו מצמצמים את מרחב החיפוש בערך בחצי, **סיבוכיות הזמן** היא $O(\log n)$. $\blacksquare$ ### סעיף ב: חיפוש איבר במערך כדי למצוא איבר `x` במערך ממוין-מסובב, נשתמש שוב בגרסה של **חיפוש בינארי**. בכל שלב, נזהה איזה חצי מהטווח הנוכחי (`[low..mid]` או `[mid..high]`) הוא רציף וממוין, ואז נבדוק אם `x` יכול להימצא באותו חצי. **תיאור האלגוריתם:** נאתחל `low = 0` ו-`high = n-1`. כל עוד `low <= high`: 1. נחשב `mid = floor((low + high) / 2)`. 2. אם `A[mid] == x`, מצאנו את האיבר ומחזירים את `mid`. 3. נבדוק איזה חצי מהמערך ממוין: - אם `A[low] <= A[mid]`: החצי השמאלי, `A[low..mid]`, ממוין. - אם `x` נמצא בטווח של החצי הממוין הזה (`A[low] <= x < A[mid]`), נמשיך לחפש בחצי השמאלי: `high = mid - 1`. - אחרת, `x` חייב להיות בחצי הימני: `low = mid + 1`. - אחרת (כלומר `A[low] > A[mid]`): החצי הימני, `A[mid..high]`, ממוין. - אם `x` נמצא בטווח של החצי הממוין הזה (`A[mid] < x <= A[high]`), נמשיך לחפש בחצי הימני: `low = mid + 1`. - אחרת, `x` חייב להיות בחצי השמאלי: `high = mid - 1`. 4. אם הלולאה הסתיימה ו-`x` לא נמצא, נחזיר "לא קיים". **נכונות וסיבוכיות:** בכל שלב, האלגוריתם מזהה נכונה איזה משני חצאי המערך ממוין. לאחר מכן, הוא בודק האם הערך המבוקש `x` נמצא בטווח הערכים של החלק הממוין. אם כן, החיפוש מצטמצם לחלק זה. אם לא, מובטח שהוא יכול להימצא (אם בכלל) רק בחלק השני. מאחר שבכל שלב מרחב החיפוש קטן בחצי, **סיבוכיות הזמן** היא $O(\log n)$. $\blacksquare$ ### סעיף ג: מקרה קצה עם כפילויות כאשר איברי המערך אינם בהכרח שונים, האלגוריתם מסעיף א' למציאת המינימום עלול להחזיר תשובה שגויה. הבעייתיות נוצרת כאשר `A[mid] == A[high]`. במצב זה, האלגוריתם מניח שהמינימום נמצא בחצי השמאלי (`high = mid`), אך ייתכן שהמינימום נמצא דווקא בחצי הימני שנזרק מטווח החיפוש. **דוגמה נגדית:** ניקח את המערך `A = [3, 3, 3, 1, 3]`. מערך זה הוא סיבוב של המערך הממוין `[1, 3, 3, 3, 3]`. האיבר המינימלי הוא `1` באינדקס `3`. נריץ את האלגוריתם מסעיף א' על מערך זה: 1. **אתחול:** `low = 0`, `high = 4`. 2. **איטרציה 1:** - `mid = floor((0+4)/2) = 2`. - `A[mid] = A[2] = 3`. - `A[high] = A[4] = 3`. - התנאי `A[mid] <= A[high]` מתקיים (כי `3 <= 3`). - האלגוריתם מסיק שהמינימום בחצי השמאלי ומעדכן: `high = mid = 2`. 3. **מצב נוכחי:** טווח החיפוש החדש הוא `[0, 2]`, כלומר תת-המערך `[3, 3, 3]`. **האיבר המינימלי `1` שהיה באינדקס `3` נזרק מטווח החיפוש.** האלגוריתם ימשיך לרוץ על הטווח `[0, 2]`, ובסופו של דבר יחזיר את אחד האינדקסים בטווח זה (למשל `0`) המכיל את הערך `3`, כתשובה שגויה. הכשל נובע מכך שבמקרה של כפילויות, לא ניתן להסיק בוודאות באיזה צד נמצא המינימום רק מהשוואה בין `A[mid]` ל-`A[high]`. $\blacksquare$