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

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

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

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

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

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

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

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

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

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

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

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

אני דאג לויד. זה CS50.