חיפוש בינארי - אחת הדרכים הקלות ביותר כדי למצוא רכיב במערך

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

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

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

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

זהו מערך של 1 ל h תחת השם "massiv", משתנה המציין את הגבול התחתון של חיפוש, שנקרא "niz", הגבול העליון, שנקרא "Verh", מונח החיפוש הממוצע - "sredn"; ואת המספר הדרוש - "ISK".

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

niz: = 1;
Verh: = h + 1;

ואז לארגן את המחזור "עד התחתון הוא פחות מ מהגבול העליון":

בעוד niz מתחיל

בכל שלב, אנו מחלקים את הקטע 2:

sredn: = (niz + Verh) div 2; {השתמש div הפונקציה, כי הפער ללא שארית}

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

אם sredn = ISK אז לשבור;

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

אם massiv [sredn]> ISK אז Verh: = sredn;

ואם להיפך, זה הופך את הגבול התחתון:

niz אחר: = sredn;
בסופו;

זה כל מה שיהיה בתוכנית.

הבה נבחן איך זה ייראה השיטה הבינארית בפועל. קח מערך זה: 1, 3, 5, 7, 10, 12, 18 וזה יבקש את המספר 12.

בסך הכל יש לנו 7 אלמנטים, כך יהיה המדיום הרביעי, הערך 7.

מאז יותר מ 12, 7, 1.3 ו 5 אלמנטים, אנו יכולים להשליך. אז יש לנו את המספר 4, 4/2 שיירינ הוא 2. אז, אלמנט חדש יהיו ממוצע של 10.

מאז 12 עולה 10, אנו להשליך 7. נשארנו רק 10, 12 ו 18.

כאן, האלמנט האמצעי הוא כבר 12, הוא המספר הדרוש. משימה זו הושלמה - מספר 12 מצא.