Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [חיפוש שכבות]
[פטריק שמידט, אוניברסיטת הרווארד]
[This Is CS50.] [CS50.TV]
חיפוש הוא משהו שאתה כנראה עושה לעתים קרובות יותר ממה שאתה חושב.
ברור, בכל פעם שאתה פותח את דפדפן אינטרנט
וחפש דף אינטרנט -
או לחפש את החברים שלך באתר הרשתות החברתי האהוב עליך -
אתה מחפש.
אבל זה רק חלק קטן מהחיפושים שאתה עושה על בסיס יומי.
כאשר אתה רוצה למצוא את החולצה כחולה שאחד בארון,
או שחולצה אדומה מושלמת לאירוע,
אתה מחפש.
כשאתה הולך לחנות שאתה אף פעם לא היית בעבר,
ואתה מחפש את הברוקולי במעבר התוצרת
אתה מחפש.
מה שאולי התחיל לשים לב
הוא שתלוי מה אתם מחפשים
או איך את הפריטים מאורגנים כאשר אתה מחפש אותם
יש לו השפעה על אופן שאתה מחפש.
לדוגמה, אם החולצות שלך תלויות בארון,
אתה בטח יכול פשוט לקחת את זה בלי הרבה חיפושים.
אם אתה יוצא מההנחה שיש לך ללכת במורד המעבר
כדי לקבל את ברוקולי, בוודאי יש לך להסתכל על כל שאר הירקות
לפני שאתה מוצא את הברוקולי ש.
חיפוש ליניארי הוא דוגמה לשיטה אחת כגון חיפוש - או אלגוריתם.
כפי שהשם מרמז,
בשיטה זו מחפשת פריט באופן ליניארי, אחד אחרי השני.
לכן, כאשר אתה מסתכל על התוצאות ממנוע החיפוש מועדף עליך
ואתה קורא את רשימת התוצאות,
אתה משתמש בחיפוש ליניארי.
אוקיי. בואו נסתכל על דוגמה.
אומר שיש לנו רשימה של מספרים - 2, 4, 0, 5, 3, 7, 8, ו 1 -
ואנחנו מחפשים מספר 0.
ברור, אתה יכול רק לראות כי 0 הוא בעמדה השלישית.
אבל, תכנית מחשב היא לא כל כך ברת מזל.
זה רק יכול "לראות" מספר אחת בכל פעם.
אז, החל בתחילת הרשימה,
זה רק "רואה" 2.
התכנית אז בודקת - הן 2 שווים 0?
ברור שלא. אז זה ממשיך והמספר הבא, 4.
האם 4 0 שווים? לא.
הבא, 0. אה! אפס שווה 0.
יש לנו את זה! זה במקום השלישי.
אוקיי. בואו נסתכל על כמה pseudocode.
זה רק כמה שורות ארוכות, אבל בואו נסתכל על זה שורה אחת בכל פעם.
ראשית, הבה תגדיר את התפקיד - ואנחנו הולכים לקרוא לזה חיפוש ליניארי -
וזה לוקח שני טיעונים - מפתח ומערך.
המפתח הוא שהערך שאנחנו מחפשים,
כך בדוגמא הקודמת, שהיה אפס.
מערך הוא רשימה של מספרים
כי יש את כל הערכים שאנחנו הולכים לחפש.
אז, מה שאנחנו רוצים לעשות הוא שאנחנו רוצים להסתכל על -
מכל התפקידים, כך מתחילים ממש בתחילתו של המערך
til סופו של המערך - ולכן האורך של המערך -
מסתכל על כל אחת עמדה ולבדוק כל אחד.
אז זה מה ש" עבור "הלולאה עושה.
ובכל מצב, אנחנו הולכים לומר
"האם זה ערך שבעמדה שווה למפתח שאנחנו מחפשים נוכחית?"
לכן - בדוגמא הקודמת שוב, מפתח היה 0 -
ולכן אנחנו אומרים "האם המערך בעמדתי שווה לאפס?"
אם זה הוא, שאנחנו הולכים לחזור 'i', כי זה תפקידו הנוכחי אנחנו ב.
לכן, בדוגמא הקודמת,
שהיה המקום השלישי.
אם עברתי על כל המערך
ואנחנו לא מצאנו דבר -
אז בואו נגיד שאנחנו מחפשים מספר 500
שברור שלא היה שבדוגמה -
אנחנו צריכים להחזיר משהו,
ואנחנו הולכים להחזיר -1.
ואנחנו רק חוזרים -1 כי זה תפקיד
שאינו קיימים במערך.
ואז זה אומר שכשאתה מקבל אותו בחזרה מפונקציה
זה אומר "הממ, אוקיי. אני מניח שאני לא מצאתי שום דבר.
כך שמעולם לא היו שם 500 ".
הדבר הנחמד הוא שחיפוש ליניארי
זה יעבוד בכל רשימה של פריטים,
לא משנה כמה את פריטי דעת מסודרות.
זה לא משנה איפה את הברוקולי הוא במעבר התוצרת.
כל עוד אתה הולך במעבר מההתחלה ועד הסוף,
אתה חייב למצוא אותו,
בהנחת שהחנות לא נגמר של ברוקולי, כמובן.
אבל כוחו הגדול ביותר שלו הוא גם החולשה הגדולה ביותר שלו.
תגיד יש לך רשימה של 200 מספרים
שמסודרים 1-200.
אם אתה מחפש את המספר 198,
אתה צריך לחפש כמעט כל הרשימה של מספרים
לפני שתמצא את זו שאתה מחפש.
חייבת להיות דרך טובה יותר!
היה סמוך ובטוח שיש.
אבל, זה נושא לוידאו אחר.
כמו כן, אל תדאגו!
רק בגלל החיפוש ליניארי הוא לא הפתרון הטוב ביותר בכל המצבים,
זה לא אומר שזה לא שימושי.
אחרת, איך אפשר לדעת שהברוקולי במעבר התוצרת?
השם שלי הוא פטריק שמידט, וזה CS50.
[CS50.TV]