[השמעת מוסיקה] 

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

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

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

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

אבל יש תניה. חיפוש בינארי יכול רק לחפש באמצעות רשימות ממוינות. מדוע זה כך? 

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

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

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

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

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

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

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

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

כי אני שווה 0, האלמנט הראשון לn מינוס 1, אתה הולך כדי להשוות כל הערך הבא אחרי זה ולמצוא המדד של הערך המינימאלי. ברגע שתמצא את אינדקס הערך המינימאלי, אתה יכול להחליף ערך זה של מערך I. מינימום והמערך 

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

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

[השמעת מוסיקה]