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

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

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

עבור מאמר זה, האלגוריתמים יתרכזו בקביעה אם קיים ערך.

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

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

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

אלגוריתם חיפוש רציף לוקח רשימת ערכים והפריט הרצוי ברשימה כפרמטרים שלו. תוצאת ההחזרה מאתחלת כ- שֶׁקֶר וישתנה ל נָכוֹן כאשר נמצא הערך הרצוי.

ראה דוגמה ליישום Python להלן:

def linearSearch (mylist, item):

נמצא = שקר

אינדקס = 0

בעוד index

אם mylist [index] == פריט:

נמצא = נכון

אַחֵר:

אינדקס = אינדקס+1

החזרה נמצאה

ניתוח אלגוריתם

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

תרחיש המקרים הממוצע באלגוריתם לעיל הוא n/2.

קָשׁוּר: מהו סימון Big-O?

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

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

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

קח דוגמא לחיפוש 19 ברשימה הנתונה: [2, 5, 6, 11, 15, 18, 23, 27, 34]. לאחר שהגיע לגיל 23, יתברר כי הפריט אותו מחפשים אינו קיים ברשימה. לכן, כבר לא יהיה חשוב להמשיך ולחפש את שאר פריטי הרשימה.

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

ראית כיצד רשימה מסודרת יכולה להפחית את החישוב הדרוש. אלגוריתם החיפוש הבינארי מנצל עוד יותר את היעילות הזו שמציגה רשימה מסודרת.

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

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

קָשׁוּר: מהו רקורסיה וכיצד משתמשים בו?

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

תהליך זה חוזר על עצמו עד שנמצא ערך אם הוא קיים.

יישום Python להלן מיועד לאלגוריתם החיפוש הבינארי.

def binarySearch (mylist, item):

נמוך = 0

high = len (mylist) - 1

נמצא = שקר

בעוד נמוך <= גבוה ולא נמצא:

אמצע = (נמוך + גבוה) // 2

אם mylist [mid] == פריט:

נמצא = נכון

פריט elif

גבוה = אמצע - 1

אַחֵר:

נמוך = אמצע + 1

החזרה נמצאה

ניתוח אלגוריתם

התרחיש הטוב ביותר מתרחש כאשר נמצא שהפריט הרצוי הוא הפריט האמצעי. אולם התרחיש הגרוע ביותר אינו פשוט. עקוב אחר הניתוח שלהלן:

לאחר ההשוואה הראשונה לא יישארו 2 פריטים. לאחר השני יישארו n/4 פריטים. לאחר השלישי, n/8.

שימו לב שמספר הפריטים ממשיך במחצית עד שהם מגיעים ל- n/2i כאשר i הוא מספר ההשוואות. אחרי כל הפיצול, יש לנו רק פריט אחד.

זה מרמז:

n/2i = 1

לכן, חיפוש בינארי הוא O (log n).

ממשיכים למיון

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

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

אופן השימוש במיון בחירה

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

קרא הבא

על הסופר