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

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

# Takes an array (Values) and a value (v).
# Returns the position of the largest value less than v.
# Note that the array (Values) must be sorted.
Less-Than-Pos(Values, v)
1	return Less-Than-Pos'(Values, v, 1, Length(Values))


# Takes an array (Values), a value (v), and two boundaries (left and right).
# Returns the position of the largest value less than v.
# Note that the array (Values) must be sorted.
Less-Than-Pos'(Values, v, left, right)
1	if left > right
2		return right
		
3	mid = ⌊(left + right) / 2⌋
		
4	if v <= Values[mid]
5		return Less-Than-Pos'(Values, v, left, mid - 1)

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

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

הוכחה: האינדוקציה היא על right - left + 1 (אורך התחום). נקרא לכך $\displaystyle n$.

(בסיס האינדוקציה) אם האורך $\displaystyle n$ הוא 0 או 1, אז מהתבוננות בקוד, הטענה נכונה.

(מעבר האינדוקציה) נניח שהטענה נכונה לכל $\displaystyle n'<n$. אם 4 מתקיימת, אז v קטן מValues[mid] (או שווה לו); מספיק לכן לבדוק את האינדקס מבין האיברים בתחום השמאלי. עפ"י הנחת האינדוקציה, נקבל את התשובה הנכונה. באופן דומה, אם 6 מתקיימת, אז נקבל את התשובה הנכונה.

נוכיח שהסיבוכיות היא $\displaystyle \Theta (\log(n))$.

הוכחה: קל לראות שנוסחת הנסיגה של הפונקציה היא $\displaystyle T(n)=T(n/2)+O(1)$. המשך ההוכחה דומה לאחת הדוגמות שראינו בפרישה.

נממש את הפונקציה המבוקשת בעזרת פונקציית העזר:

Find-Num-In-Range(A, a, b)
1	return Less-Than-Pos(A, b) - Less-Than-Pos(A, a + 1)

נוכיח נכונות.

הוכחה: נתבונן בLess-Than-Pos(A, b).

1. אם האינדקס הוא 0, אז כל האיברים גדולים מ$\displaystyle b$.
2. אם אינו 0, אז כל איבר שמימינו (אם יש) גדול מ$\displaystyle b$ או שווה לו, וכל איבר שמשמאלו קטן ממש מ$\displaystyle b$.

נתבונן בLess-Than-Pos(A, a + 1).

1. אם האינדקס הוא Length(A) + 1, אז כל האיברים קטנים מ$\displaystyle a$ או שווים לו.
2. אם אינו 0, אז כל איבר שמשמאלו הוא לכל היותר $\displaystyle a$, וכל איבר בו או מימינו (אם יש) גדול ממש מ$\displaystyle a$.

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

קל לראות שהסיבוכיות היא $\displaystyle \Theta (\log(n))$, משום שהאלגוריתמים מורכב משתי קריאות לפונקציית העזר שבנינו.