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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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