תוכן עניינים:
הגדרה - מה המשמעות של חיפוש בינארי?
אלגוריתם חיפוש בינארי משמש למציאת המיקום של ערך ספציפי הכלול במערך ממוין. בעבודה עם עיקרון ההפרדה והכיבוש, אלגוריתם החיפוש הזה יכול להיות מהיר למדי, אך האזהרה היא שהנתונים צריכים להיות בצורה ממוינת. זה עובד על ידי התחלת החיפוש באמצע המערך ועבודה בירידה במחצית התחתונה או העליונה של הרצף. אם הערך החציוני נמוך מערך היעד, פירוש הדבר שהחיפוש צריך להיות גבוה יותר, אם לא, הוא צריך להסתכל על החלק היורד של המערך.
חיפוש בינארי מכונה גם חיפוש של חצי מרווחים או חיפוש לוגריתמי.
Techopedia מסביר על חיפוש בינארי
חיפוש בינארי הוא שיטה מהירה ויעילה למציאת ערך יעד ספציפי מתוך סט פריטים שהוזמנו. על ידי התחלה באמצע הרשימה הממוינת, היא יכולה למעשה לחתוך את שטח החיפוש לשניים על ידי קביעה אם לעלות או לרדת לרשימה על סמך הערך החציוני לעומת ערך היעד.
לדוגמה, עם ערך יעד של 8 ומרחב חיפוש של 1 עד 11:
- הערך החציוני / אמצעי נמצא והמצביע מוגדר שם, שבמקרה זה הוא 6.
- היעד של 8 מושווה ל 6. מכיוון ש 6 קטן מ- 8, היעד צריך להיות במחצית הגבוהה.
- המצביע מועבר לערך הבא (7) ומשווה אותו למטרה. הוא קטן יותר, ולכן המצביע עובר לערך הגבוה הבא.
- המצביע נמצא כעת על 8. בהשוואה למטרה זו התאמה מדויקת, ולכן היעד נמצא.
באמצעות חיפוש בינארי, היה צורך להשוות את היעד לשלושה ערכים בלבד. בהשוואה לביצוע חיפוש לינארי, זה היה מתחיל מהערך הראשון ועובר למעלה וצריך להשוות את היעד לשמונה ערכים. חיפוש בינארי אפשרי רק עם סט נתונים מסודר; אם הנתונים מסודרים באופן אקראי, אז חיפוש לינארי יביא תוצאות כל הזמן ואילו חיפוש בינארי כנראה יתקע בלולאה אינסופית.
