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

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

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

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

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

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

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

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

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

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