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

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

דף זה עוסק במציאת איבר במערך, לדוגמה, מציאת 7 במערך בתרשים הבא.

בעיית החיפוש.

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

חיפוש לינארי

הרעיון הבסיסי

חיפוש לינארי הוא פשוט מאד: עוברים על המערך משמאל לימין ב"קו" (ומכאן שמו, linear מלשון line), עד שמוצאים את האיבר המבוקש, או מגיעים לסוף המערך.

פסאודו-קוד

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

# Linear search.   
# Takes an array (Values) and a value (v).
# Returns an element if it matches the value (v), Nil otherwise.
Linear-Search(Values, v)
1	for i in [1, ..., Length(Values)]
2		if Values[i] == v
3			return Values[i]
		 		
4	return Nil

להלן הסבר לקוד. 1-3 עוברות בלולאה על איברי תבנית:קוד בשורה. אם 2 מוצאת איבר שהוא האיבר המבוקש תבנית:קוד בשורה, מחזירים אותו (או מצביע אליו) ב3. אם לא נמצא האיבר המבוקש, מחזירים ערך ריק (או מצביע ריק) ב4.

מהי שפת התיכנות בה הקוד כתוב? זו אינה שפת תכנות אמיתית. היא מזכירה מעט גרסה מפושטת של שפת C (או, יותר מכך, פייתון). המטרה היא רק לכתוב את הרעיון כך שמי שיודע שפה כלשהי, יוכל לתרגם אותו בקלות לאותה שפה. בכל זאת, נשים לב למספר נקודות:

• אין צורך להגדיר טיפוסים של משתנים או פונקציות. אין צורך להגדיר האם משהו הוא משתנה או מצביע למשתנה. יש להבין את הדברים הללו מתוך ההקשר.
• אין צורך להשתמש בסוגריים מסולסלים כדי לתאר את הבלוק של פונקציה, תנאי, או לולאה. ההזחה משמשת לצורך כך.
• המערכים הנם מבוססי-1, כלומר האינדקס של איברם הראשון הוא 1 (שלא כבC, שם הוא 0).
• תבנית:קוד בשורה הוא ערך מיוחד המסמן "כלום" (בדומה לNULL בשפת C).
• אם תבנית:קוד בשורה הוא מערך, אז תבנית:קוד בשורה מחזיר את ארכו.

תבנית:הארה

הוכחת נכונות

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

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

כאן בהקשר חיפוש לינארי, הוכחת הנכונות היא טריוויאלית. נוכיח בכל זאת את הנכונות כדי להתרגל לצורת ההוכחה. תבנית:הוכחה

ניתוח סיבוכיות

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

נקבע את $n$ כתבנית:קוד בשורה.‏ כמה זמן אורכת שורה 2 במדויק? אי אפשר לדעת: זה תלוי במספר גורמים, כמו חומרת המחשב או שפת התכנות. לעומת זאת, נתן לדעת בוודאות שזמן זה הוא גודל חיובי (ממש) שאינו תלוי ב$n$.

לא כל הדברים הם $\mathrm{\Theta }(1)$. לדוגמה, 2-3 אכן $\mathrm{\Theta }(1)$, אבל 1-3 אינם $\mathrm{\Theta }(1)$, מפני שאורך הלולאה תלוי בגודל הקלט $n$. בנקודה זו נוכל לומר, אבל, שאם תבנית:קוד בשורה נמצא בתבנית:קוד בשורה אז תבנית:קוד בשורה אורכת $\mathrm{\Theta }(1)+\mathrm{\Theta }(1)\cdot n+\mathrm{\Theta }(1)$ זמן במקרה הגרוע (שהוא כאשר האיבר שאותו מחפשים הוא האחרון בתבנית:קוד בשורה):

• הקריאה לפונקציה היא $\mathrm{\Theta }(1)$.
• הלולאה 1-3 (ובפרט שורות 1-2) מתבצעת $n$ פעמים (במקרה הגרוע), וכל איטרציה אורכת $\mathrm{\Theta }(1)$ זמן.
• השורה 3 מתבצעת פעם אחת והיא $\mathrm{\Theta }(1)$.

נצייר גרף של $\mathrm{\Theta }(1)+\mathrm{\Theta }(1)\cdot n+\mathrm{\Theta }(1)$:

זמן הריצה של חיפוש לינארי.

נשים לב שאיננו יודעים הרבה מעבר לצורת הגרף. ייתכן שהפונקציה דומה ל$300+3\cdot n$, וייתכן שהפונקציה דומה ל$3+300\cdot n$ (כל אחת מהן היא מהצורה $\mathrm{\Theta }(1)+\mathrm{\Theta }(1)\cdot n+\mathrm{\Theta }(1)$). בכל אופן, מדובר בפונקציה לינארית.

חיפוש בינרי

הרעיון הבסיסי

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

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

התרשים הבא מראה את התחומים הראשונים בהם אנו מחפשים את 7:

מספר שלבים בחיפוש בינרי.

תבנית:הארה

תבנית:מבנה תבנית

תבנית:משימה

פסוודו-קוד

# Binary search. 
# Takes an array (Values) and a value (v).
# Returns an element if it matches the value (v), Nil otherwise.
# Note that the array (Values) must be sorted.
Binary-Search(Values, v)
1	return Binary-Search'(Values, v, 1, Length(Values))


# Binary search implementation. 
# Takes an array (Values), a value (v), and two boundaries (left and right).
# Returns an element if it matches the value (v), Nil otherwise.
# Note that the array (Values) must be sorted.
Binary-Search'(Values, v, left, right)
1	if left > right
2		return Nil
		
3	mid = ⌊(left + right) / 2⌋
		
4	if v < Values[mid]
5		return Binary-Search'(Values, v, left, mid - 1)

6	if v > Values[mid]
7		return Binary-Search'(Values, v, mid + 1, right)

8	return Values[mid]

הפונקציה תבנית:קוד בשורה אינה עושה דבר מלבד לקרוא לתבנית:קוד בשורה ולהחזיר את הערך המוחזר ממנה. בפונקציה תבנית:קוד בשורה, המשתנים תבנית:קוד בשורה ותבנית:קוד בשורה הם "גבולות הגזרה" של תחום החיפוש. (תבנית:קוד בשורה תחילה קובעת אותם לאינדקס הראשון והאחרון של כל המערך, בקריאה הראשונה). 3 מחשבת את האינדקס האמצעי, 4-5 ו6-7 בודקות האם לחפש בתת-תחום שמאלי או ימני, ו8 מטפלת במקרה בו נמצא האיבר.

הוכחת נכונות

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

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

כעת נוכיח שהערך המוחזר נכון. תבנית:הוכחה

ניתוח סיבוכיות

שוב, נקבע את $n$ כתבנית:קוד בשורה.

נגדיר את זמן הריצה של תבנית:קוד בשורה על קלט בגודל $n$ כ$T(n)$.

כ"א מ1, 2, ו3, 4, 6, ו8, אורכת $\mathrm{\Theta }(1)$ זמן (הן אינן תלויות בגודל הקלט $n$). לכן, אם 8 אינה מתבצעת, אז האיטרציה הבאה תפעל על תחום שגודלו$\lfloor (n-1)/2\rfloor$. מכאן נקבל $T(n)=T(\lfloor (n-1)/2\rfloor )+\mathrm{\Theta }(1)$.

בהמשך נראה שהפונקציה היא לוגריתמית, פחות או יותר. כלומר, פחות או יותר, $T(n)=\mathrm{\Theta }(1)\cdot (\log (n+1)+\mathrm{\Theta }(1))$. מכאן נקבל שזמן הריצה של תבנית:קוד בשורה, שהוא $\mathrm{\Theta }(1)+T(n)$, הנו $\mathrm{\Theta }(1)+T(n)=\mathrm{\Theta }(1)+\mathrm{\Theta }(1)\cdot (\log (n+1)+\mathrm{\Theta }(1))$. שוב, נצייר ביטוי זה:

זמן הריצה של חיפוש בינרי.

נשים לב שאיננו יודעים הרבה מעבר לצורת הגרף. ייתכן שהפונקציה דומה ל$300+3\cdot (\log (n+1)+50)$, וייתכן שהפונקציה דומה ל$3+300\cdot (\log (n+1)+50)$ (כל אחת מהן היא מהצורה $\mathrm{\Theta }(1)+T(n)=\mathrm{\Theta }(1)+\mathrm{\Theta }(1)\cdot (\log (n+1)+\mathrm{\Theta }(1))$). בכל אופן, מדובר בפונקציה לוגריתמית.

השוואה בין שתי שיטות החיפוש

ראינו שתי שיטות חיפוש בדף זה, חיפוש לינארי וחיפוש בינרי. יש ביניהן מספר הבדלים. בין היתר:

1. הראשונה עובדת לכל מערך, והשניה עובדת למערך ממויין.
2. יש להם זמני ריצה שונים עבור המקרה הגרוע ביותר של מציאת איבר שאכן נמצא במערך.

נתמקד מעט בנקודה השניה. אנו יודעים שזמן הריצה של חיפוש לינארי במקרה הגרוע הוא $\mathrm{\Theta }(1)+\mathrm{\Theta }(1)\cdot n+\mathrm{\Theta }(1)$, כלומר משהו כזה:

זמן הריצה של חיפוש לינארי.

אנו יודעים שזמן הריצה של חיפוש בינרי במקרה הגרוע הוא $\mathrm{\Theta }(1)+\mathrm{\Theta }(1)\cdot (\log (n+1)+\mathrm{\Theta }(1))$, כלומר משהו כזה:

זמן הריצה של חיפוש בינרי.

למרות שאנו יודעים מעט מאד על זמני הריצה של שתי הפונקציות (לדוגמה, איננו יודעים האם הראשונה היא $300+3\cdot n$ או $3+300\cdot n$), קל מאד לראות שעבור קלטים גדולים מספיק, המקרה הגרוע של חיפוש בינרי הוא הרבה יותר מהיר מהמקרה הגרוע של חיפוש לינארי. מספיק לזהות שהראשונה היא פונקציה לינארית, והשניה היא פונקציה לוגריתמית.

סיכום

בדף זה הגדרנו בעיה, ראינו שני אלגוריתמים שפותרים אותה, והשווינו ביניהם. שני הרעיונות החשובים שראינו הם אלגוריתמים וסדרי גדילה:

1. אלגוריתם הוא סידרת פעולות מוגדרת היטב שפותרת בעיה בזמן סופי. כדי להראות שרעיון לפיתרון בעיה הוא אלגוריתם, צריך לתאר את הפיתרון (במילים ובציורים כדי להבינו, ובפסוודו-קוד כדי לתארו בצורה מדוייקת יותר), ולהוכיח שפעולתו סופית ונכונה.
2. כדי לבחור איזה אלגוריתם פועל טוב יותר (עבור קלטים גדולים מספיק), אפשר לנתח את סדר הגדילה של כל אלגוריתם, כלומר, לזהות שאלגוריתם גדל "כמו לוגריתם", או "כמו פונקציה לינארית".

תבנית:מבני נתונים ואלגוריתמים - מחברת קורס