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

2024 מְחַבֵּר: Lynn Donovan | [email protected]. שונה לאחרונה: 2023-12-15 23:47

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

באופן דומה, אנשים שואלים, איך מוצאים חיפוש בינארי?

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

באופן דומה, מהו ה-O הגדול של החיפוש הבינארי? חיפוש בינארי הוא למעשה א לחפש פעולה על BST מאוזן ( חיפוש בינארי עֵץ). כמו לחפש יש מורכבות זמן של O (לוג n). ראה, המערך הממוין שלך עשוי להיראות בתור עומק ראשון לחפש סדרת סדרה של BST מאוזן. כלומר, בצע רקורסיבית את הפעולות הבאות (החל מהשורש):

יודע גם, מהם 7 השלבים של חיפוש בינארי?

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

• שלב 1 - קרא את רכיב החיפוש מהמשתמש.
• שלב 2 - מצא את האלמנט האמצעי ברשימה הממוינת.
• שלב 3 - השוו את אלמנט החיפוש לאלמנט האמצעי ברשימה הממוינת.
• שלב 4 - אם שניהם מתאימים, הצג את "האלמנט נתון נמצא!!!" ולסיים את הפונקציה.

איך עובד חיפוש בינארי?

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