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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

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

# 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 (אורך התחום). נקרא לכך .

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

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

מש"ל.PNG

נוכיח שהסיבוכיות היא .


הוכחה: קל לראות שנוסחת הנסיגה של הפונקציה היא . המשך ההוכחה דומה לאחת הדוגמות שראינו בפרישה.

מש"ל.PNG


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

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, אז כל האיברים גדולים מ.
  2. אם אינו 0, אז כל איבר שמימינו (אם יש) גדול מ או שווה לו, וכל איבר שמשמאלו קטן ממש מ.

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

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

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

מש"ל.PNG

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