חיפוש בינארי

ל חיפוש בינארי , המכונה גם א חיפוש חצי מרווח , הוא אַלגוֹרִיתְם משמש במדעי המחשב לאיתור ערך מוגדר (מפתח) בתוך מַעֲרָך . כדי שהחיפוש יהיה בינארי, על המערך להיות מְמוּיָן בסדר עולה או יורד.

איך זה עובד?

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

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



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