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

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

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

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

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

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

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

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

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

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

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

אז אנחנו לחשב את נקודת האמצע על ידי הוספת 0 בתוספת 14 חלקי 2; נקודת אמצע די פשוט. ואנחנו יכולים לומר ש נקודת האמצע הוא כעת 7. אז הוא 15 מה שאנחנו מחפשים? לא זה לא. אנחנו מחפשים 19. אבל אנחנו יודעים כי 19 הוא גדולים יותר ממה שמצאנו באמצע. 

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

ועכשיו, אנחנו הולכים על זה שוב. אנו מחשבים את נקודת האמצע החדשה. 8 + 14 הוא 22, מחולקים ב2 הוא 11. האם זה מה שאנחנו מחפשים? לא זה לא. אנחנו מחפשים ערך זה פחות ממה שאנחנו פשוט מצאנו. אז אנחנו הולכים לחזור התהליך שוב. אנחנו הולכים לשנות את נקודת הסיום ל להיות רק בצד השמאל של נקודת האמצע. אז נקודת הסיום החדשה הופכת 10. ועכשיו, זה רק החלק מ המערך אנחנו צריכים למיין. אז יש לנו עכשיו בוטלו 12 מתוך 15 המרכיבים. אנחנו יודעים שאם 19 קיים במערך, זה חייב להתקיים אי שם בין האלמנט מספר 8 ומספר 10 אלמנט. 

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

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

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

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

עכשיו, אנו חוזרים לעבד עוד פעם אחת. לחשב את נקודת האמצע החדשה. 8 + 14 הוא 22, מחולקים ב2 הוא 11. האם 23 מה אנחנו מחפשים? למרבה הצער לא. אנחנו מחפשים ערך כי הוא פחות מ -23. ולכן במקרה זה, אנחנו הולכים כדי לשנות את נקודת הסיום להיות פשוט מהשמאל לנקודת האמצע הנוכחי. נקודת האמצע הנוכחית היא 11, ו כך תהיה לנו להגדיר את נקודת הסיום החדשה לפעם הבאה שאנחנו הולכים בתהליך זה עד 10. 

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

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

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

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

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

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

אני דאג לויד. זה 50 CS.