חיפוש בינארי הוא אחת הדרכים הקלות ביותר למצוא אלמנט במערך
לעתים קרובות, מתכנתים, אפילו מתחילים,כי יש סדרה של מספרים בהם יש צורך למצוא מספר מסוים. אוסף זה נקרא מערך. וכדי למצוא את היסוד הנכון בו, יש הרבה דרכים. אבל הפשוטה ביניהם על ידי הזכות יכול להיחשב חיפוש בינארי. מהי השיטה? וכיצד ליישם חיפוש בינארי? פסקל הוא המדיום הפשוט ביותר לארגון תוכנית כזו, ולכן נשתמש בה לצורך מחקר.
ראשית, ננתח מה היתרונות של שיטה זו הם, אחרי הכל, כדי שנוכל להבין,
אז, מה הוא עקרון העבודה של זהשיטה? כדאי להזכיר שחיפוש בינארי אינו פועל במערך כלשהו, אלא רק במערך של מספרים ממוינים. בכל שלב הבא, האלמנט האמצעי של המערך (מתייחס למספר האלמנט) נלקח. אם המספר הרצוי גדול מהממוצע, אז כל מה שנמצא בצד שמאל, כלומר, פחות מהאלמנט הממוצע, ניתן להשליך ולא לחפש שם. לעומת זאת, אם פחות מהממוצע, בין המספרים בצד ימין, אתה לא יכול לחפש אותם. לאחר מכן, נבחר אזור חיפוש חדש, שבו האלמנט האמצעי של המערך כולו יהיה האלמנט הראשון, והאחרון יישאר האחרון. המספר הממוצע של השטח החדש יהיה ¼ של כל הקטע, כלומר (האלמנט האחרון + האלמנט הממוצע של המערך כולו) / 2. שוב, אותה פעולה מבוצעת - השוואה למספר הממוצע של המערך. אם הערך הרצוי נמוך מהממוצע, מחק את הצד הימני, ועשה את אותו הדבר עד שיימצא האלמנט האמצעי.
כמובן, זה הכי טוב להסתכל על דוגמה של איך בינארי החיפוש נכתב. פסקל כאן מתאים לכל אחד - הגרסה אינה חשובה. בואו נכתוב תוכנית פשוטה.
זה יהיה מערך בין 1 ל h בשם"massiv", משתנה המציין גבול חיפוש נמוך יותר, הנקרא "niz", כריכה עליונה בשם "verh", האלמנט האמצעי של החיפוש הוא "sredn"; ואת המספר הנדרש הוא "isk".
לכן, תחילה להקצות את הגבולות העליונים והתחתונים של מרווח החיפוש:
niz: = 1;
verh: = h + 1;
לאחר מכן אנו מארגנים את מחזור "בעוד התחתון הוא פחות מהגבול העליון":
בעוד niz <verh - 1 לעשות
להתחיל
בכל שלב, לחלק את הקטע על ידי 2:
sredn: = (niz + verh) div 2; {השתמש בפונקציה div מכיוון שאנו מחלקים את השאר}
בכל פעם שאנחנו עורכים בדיקה. אם הממוצע הוא שווה לזה הרצוי, אנחנו מפסיקים את המחזור, שכן האלמנט הרצוי נמצא כבר:
אם sredn = isk ואז לשבור;
אם האלמנט הממוצע של המערך גדול יותר מזה שאנו מחפשים, מחק את הצד השמאלי, כלומר, אנו מקצים את האלמנט האמצעי לגבול העליון:
אם massiv [sredn]> isk מכן verh: = sredn;
ואם להיפך, אז אנחנו עושים את זה הגבול התחתון:
else niz: = sredn;
ח
זה כל מה שיהיה בתוכנית.
ננתח כיצד השיטה הבינארית תיראה בפועל. אנחנו לוקחים מערך כזה: 1, 3, 5, 7, 10, 12, 18 ומחפשים את המספר 12 בתוכו.
בסך הכל, יש לנו 7 אלמנטים, כך הממוצע יהיה הרביעי, הערך שלה 7.
| 1 | 3 | 5 | 7 | 10 | 12 | 18 |
מאז 12 הוא גדול מ 7, אלמנטים 1,3 ו 5 ניתן להשליך. לאחר מכן, יש לנו 4 מספרים שמאל, 4/2 ללא שארית הוא 2. אז, אלמנט הביניים החדש יהיה 10.
| 7 | 10 | 12 | 18 |
כאן האלמנט האמצעי הוא כבר 12, זה המספר הנדרש. המשימה הושלמה - המספר 12 נמצא.
