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

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

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

Less-Than-Dist(Values, v)
1	return Less-Than-Dist'(Values, v, 1, Length(Values))


Less-Than-Dist'(Values, v, left, right)
1	if left > right
2		return right
		
3	mid = ⌊(left + right) / 2⌋
		
4	if Dist(v) <= Dist(Values[mid])
5		return Less-Than-Pos'(Values, v, left, mid - 1)

6	if Dist(v) > Dist(Values[mid])
7		return Less-Than-Pos'(Values, v, mid + 1, right)

כעת נותר לטפל בפונקציה האחרונה. פונקציה זו ביצעה שתי קריאות:

• Less-Than-Dist(A, b) - כאן אין הבדל.
• Less-Than-Dist(A, a + 1) - מדוע הוספנו דווקא את המספר 1? מהתבוננות בתשובה עולה שכל שהיינו צריכים לעשות הוא להוסיף ל$\displaystyle a$ מספר שגודלו הוא לכל היותר ההפרש בין שני איברים שונים במערך. במקרה שמדובר במספרים שלמים, ההפרש בין שני מספרים שונים במערך הוא לפחות 1.

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

Find-Num-In-Range(A, a, b)
1	d = Min-Dist-Between-Two-Elements(A) # Finds the smallest distance as was just described.
2	return Less-Than-Dist(A, b) - Less-Than-Dist(A, a + d)