חיפוש בינארי בפייתון: מבוא חזותי

ברוך הבא

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

בפרט תלמד:

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

בואו נתחיל! ✨

? מבוא לחיפוש בינארי

אלגוריתם זה משמש למציאת אלמנט ברצף מסודר (לדוגמא: רשימה, tuple או מחרוזת).

דרישות

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

? טיפ: תוכלו למיין את הרצף לפני החלת חיפוש בינארי באמצעות אלגוריתם מיון העונה על צרכיכם.

קלט ופלט

האלגוריתם (המיושם כפונקציה) זקוק לנתונים אלה:

• רצף אלמנטים מסודר (לדוגמא: רשימה, tuple, מחרוזת).
• אלמנט היעד אותו אנו מחפשים.

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

יְעִילוּת

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

נתחיל לצלול אלגוריתם זה.

? הדרכה חזותית

אנו נשתמש ברשימת אלגוריתם החיפוש הבינארי:

טיפ: שימו לב שהרשימה כבר ממוינת. הוא כלל את המדדים כהפניה חזותית.

מטרה

אנו רוצים למצוא את האינדקס של המספר השלם 67 .

הַפסָקָה

בואו נעמיד פנים שאנחנו האלגוריתם. איך נתחיל בתהליך?

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

אלמנט אמצעי

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

במקרה זה, (0 + 5)//2זה 2מכיוון שהתוצאה של 5/2is 2.5וחלוקה שלמה מקטמת את החלק העשרוני.

אז האלמנט האמצעי ממוקם באינדקס 2 , והאלמנט האמצעי הוא המספר 6 :

השוואות

כעת עלינו להתחיל להשוות את האלמנט האמצעי לאלמנט היעד שלנו כדי לראות מה עלינו לעשות הלאה.

שאלנו:

האם האלמנט האמצעי שווה לאלמנט אותו אנו מחפשים?

6 == 67 # False

לא, זה לא.

אז אנחנו שואלים:

האם האלמנט האמצעי גדול מהאלמנט אותו אנו מחפשים?

6 > 67 # False

לא, זה לא.

אז האלמנט האמצעי קטן מהאלמנט שאנחנו מחפשים.

6 < 67 # True

מחק אלמנטים

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

התחל מחדש - בחר את הגבולות

מה נעשה עכשיו? השלכנו את האלמנטים והמחזור חוזר שוב.

עלינו לבחור את גבולות המרווח החדש (ראה להלן). אך שימו לב שהגבול העליון נשמר בשלמותו ורק הגבול התחתון משתנה.

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

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

אלמנט אמצעי

כעת עלינו למצוא את האינדקס של האלמנט האמצעי על ידי הוספת הגבול התחתון לגבול העליון וחלוקת התוצאה ב -2 באמצעות חלוקה שלמה.

התוצאה של (3+5)//2הוא 4, כך שהאלמנט האמצעי ממוקם באינדקס4 והאלמנט האמצעי הוא 67 .

השוואות

שאלנו:

האם האלמנט האמצעי שווה לאלמנט אותו אנו מחפשים?

67 == 67 # True

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

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

? הדרכת קוד

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

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

כּוֹתֶרֶת

הנה לנו כותרת הפונקציה:

def binary_search(data, elem):

נדרשים שני טיעונים:

• רצף האלמנטים המסודר (למשל: רשימה, tuple או מחרוזת).
• האלמנט שאנחנו רוצים למצוא.

מרווח ראשוני

השורה הבאה קובעת את הגבולות הראשונים והתחתונים הראשונים:

low = 0 high = len(data) - 1

הגבול התחתון הראשוני הוא אינדקס 0והגבול העליון הראשוני הוא האינדקס האחרון של הרצף.

לוּלָאָה

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

while low <= high:

טיפ: זכרו שהגבולות הם מדדים.

אלמנט אמצעי

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

middle = (low + high)//2

טיפ: אנו משתמשים בחלוקה שלמה למקרה שהרשימה או המרווח מכילים מספר זוגי של אלמנטים. לדוגמה, אם ברשימה היו 6 אלמנטים ולא היינו משתמשים בחלוקה שלמה, middleהתוצאה (0 + 5)/2שלהם היא 2.5. אינדקס לא יכול להיות צף, ולכן אנו מקטעים את החלק העשרוני באמצעות //ובוחרים את האלמנט באינדקס 2.

השוואות

עם תנאים אלה (ראה להלן), אנו קובעים מה לעשות בהתאם לערך האלמנט האמצעי data[middle]. אנו משווים אותו לאלמנט היעד אותו אנו מחפשים.

if data[middle] == elem: return middle elif data[middle] > elem: high = middle - 1 else: low = middle + 1

ישנן שלוש אפשרויות:

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

if data[middle] == elem: return middle

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

elif data[middle] > elem: high = middle - 1

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

else: low = middle + 1

אלמנט לא נמצא

אם הלולאה הושלמה מבלי למצוא את האלמנט, הערך -1 מוחזר.

return -1

ויש לנו את היישום הסופי של האלגוריתם לחיפוש בינארי:

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

? מקרים מיוחדים

אלה כמה מקרים ספציפיים שאתה עלול למצוא כשאתה מתחיל לעבוד עם האלגוריתם הזה:

אלמנטים חוזרים

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

>>> >>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 7) 4 

אלמנט לא נמצא

אם האלמנט לא נמצא, -1 מוחזר.

>>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 8) -1

רצף ריק

אם הרצף ריק, -1 יוחזר.

>>> b = [] >>> binary_search(b, 8) -1

רצף לא ממוין

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

דוגמה זו מחזירה את התוצאה הנכונה:

>>> b = [5, 7, 3, 0, -9, 2, 6] >>> binary_search(b, 6) 6

אבל זה לא:

>>> b = [5, 7, 3, 0, -9, 2, 10, 6] >>> binary_search(b, 6) -1

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

? דוגמה מורכבת יותר

עכשיו כשאתה מכיר יותר את האלגוריתם ואת יישום הפייתון שלו, הנה לנו דוגמה מורכבת יותר:

אנו רוצים למצוא את האינדקס של האלמנט 45 ברשימה זו באמצעות חיפוש בינארי:

איטרציה ראשונה

הגבול התחתון והתחתון נבחרים:

נבחר האלמנט האמצעי ( 26 ):

אך האלמנט האמצעי ( 26 ) אינו האלמנט אותו אנו מחפשים, הוא קטן מ- 45 :

איטרציה שנייה

כדי שנוכל להשליך את כל האלמנטים הקטנים מאלמנט האמצעי ולבחור גבולות חדשים. הגבול התחתון החדש ( 27 ) הוא האלמנט שנמצא מיד מימין לאלמנט האמצעי הקודם:

? טיפ: זכור כי הרשימה כבר ממוין.

נבחר האלמנט האמצעי החדש ( 30 ):

האלמנט האמצעי ( 30 ) אינו האלמנט אותו אנו מחפשים, הוא קטן מ 45 :

איטרציה שלישית

אנו יכולים להשליך את האלמנטים הקטנים או שווים ל 30 שטרם הושלכו. הגבול התחתון מעודכן ל -32 :

הנה לנו מקרה מעניין: האלמנט האמצעי הוא אחד מגבולות המרווח הנוכחי כי (7+8)//2הוא 7.

האלמנט האמצעי ( 32 ) אינו האלמנט אותו אנו מחפשים ( 45 ), הוא קטן יותר.

איטרציה רביעית

אנו יכולים להשליך את האלמנטים הקטנים או שווים ל 32 שטרם הושלכו.

הנה לנו עוד מקרה מעניין מאוד: לרווח יש רק אלמנט אחד.

? טיפ: מרווח זה תקף מכיוון שכתבנו תנאי זה while high <= low:, הכולל מרווחים בהם אינדקס הגבול התחתון שווה לאינדקס הגבול העליון.

האלמנט האמצעי הוא האלמנט היחיד במרווח מכיוון (8+8)//2שהוא 8, ולכן האינדקס של האלמנט האמצעי הוא 8 והאלמנט האמצעי הוא 45 .

כעת האלמנט האמצעי הוא האלמנט אותו אנו מחפשים, 45 :

אז מוחזר הערך 8 (האינדקס):

>>> binary_search([1, 3, 7, 15, 26, 27, 30, 32, 45], 45) 8

? תרגול נוסף

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

[5, 8, 15, 26, 38, 56]

• מה קורה שלב אחר שלב?
• איזה ערך מוחזר?
• האם האלמנט נמצא?

אני באמת מקווה שאהבת את המאמר שלי ומצאת אותו מועיל. עכשיו אתה יכול ליישם את האלגוריתם חיפוש בינארי בפייתון. בדוק את הקורס המקוון שלי "חיפוש ופייתון של אלגוריתמים: גישה מעשית". עקוב אחריי בטוויטר. ⭐️