חילקנו אוסף של פריטים לשני חצאים בחיפוש בינארי כדי להקטין את מספר ההשוואות הישירות הדרושות לגילוי אלמנט. עם זאת, יש דרישה אחת: יש למיין את הפריטים של המערך מראש.
חיפוש בינארי
ה חיפוש בינארי השיטה מאתרת את האינדקס של חבר רשימה מסוים. זה בין האלגוריתמים הפופולריים והמהירים ביותר. כדי שהליך החיפוש הבינארי יפעל, יש למיין את הערכים ברשימה.
חיפוש בינארי היא טכניקת חיפוש יעילה יותר לאיתור אינדקס של אלמנט מאשר חיפוש לינארי מכיוון שאנו לא צריכים לבחון כל אינדקס רשימה.
מפה java
ניתן לסכם את כל הפעולה של אלגוריתם החיפוש הבינארי בשלבים הבאים:
- אתר את האלמנט האמצעי במערך הממוין.
- ערכו השוואה בין האלמנט שיש לאתר לבין האלמנט האמצעי.
- אם האלמנט הזה שווה לאלמנט האמצעי של הרשימה הנתונה, האינדקס של האלמנט האמצעי מוחזר. אחרת, האלגוריתם ישווה את האלמנט עם הפריט שבאמצע.
- כעת, אם האלמנט שיש לאתר גדול מהפריט האמצעי של הרשימה, הוא יושווה לחצי הימני של הרשימה, כלומר אלמנטים אחרי האינדקס האמצעי.
- או אם האלמנט קטן מהאלמנט שבאמצע הרשימה, אז הוא יושווה רק לחצי השמאלי של הרשימה, כלומר אלמנטים לפני האינדקס האמצעי.
חיפוש בינארי רקורסיבי
חיפוש בינארי מרמז על חלוקה מתמדת של מרווח החיפוש ל-2 חלקים שווים כדי לגלות אלמנט במערך ממוין, וחיפוש בינארי חוזר כרוך בפירוק הליך החיפוש הבינארי המלא לבעיות קטנות יותר. חיפוש בינארי רקורסיבי הוא תשובת הרקורסיה לחיפוש בינארי.
להלן המאפיינים שפתרונות רקורסיביים חייבים לעמוד בהם:
- נדרש מקרה בסיס לגישה רקורסיבית.
- חייב להיות מקרה מבחן רקורסיבי בגישה רקורסיבית.
- גישה רקורסיבית צריכה להתקרב למקרה הבסיסי.
החלוקה הנמוכה ביותר של בעיה מסובכת מיוצגת על ידי מקרה בסיס, שהוא מקרה סופי. לכן, כדי לבצע את החיפוש הבינארי לפי שיטה רקורסיבית, האלגוריתם שלנו חייב להכיל מקרה בסיסי ומקרה רקורסיבי, כאשר המקרה הרקורסי מתקדם למקרה הבסיסי. אחרת התהליך לעולם לא יסתיים ויביא ללופ אינסופי.
טכניקת החיפוש הבינארי מפחיתה את הזמן שלוקח למצוא אלמנט מסוים בתוך מערך ממוין. שיטת החיפוש הבינארי מיושמת לעתים קרובות באופן איטרטיבי, אך אנו עשויים גם ליישם אותה רקורסיבית על ידי פירוקה לחתיכות קטנות יותר.
קוד
#defining a function to execute Binary Search on any given sorted list L. #start is the lowest index of the list being checked at any given time. #end is the highest index of the list being checked at any given time. #item is the item to be searched in the list. def binary_search(L, start, end, item): if end >= start: middle = (start + end) // 2 if L[middle] == item: return middle #middle element is the item to be located #if middle item is greater than the item to be searched, left side of the list will be searched elif L[middle] > item: #starting index will be same but ending index will be the middle of the main list i.e. left half of the list is given in function. return binary_search(L, start, middle - 1, item) else: #if middle item is smaller than the item to be searched, new starting index will be middle of the list i.e. right half of the list. return binary_search(L, middle + 1, end, item) else: #if element is not present in the list return -1 #Drivers code my_list = [ 2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22 ] element_to_search = 6 print('The given list is') print(my_list) index_of_element = binary_search(my_list, 0, len(my_list)-1, element_to_search) if index_of_element != -1: print('Element searched is found at the index ', str(index_of_element), 'of given list') else: print('Element searched is not found in the given list!')
תְפוּקָה:
The given list is [2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22] Element searched is found at the index 2 of given list
רקורסיה היא טכניקת תכנות ופתרון בעיות חזקה במיוחד. אנו עשויים להשתמש בו כדי להעריך ולבצע מגוון אלגוריתמים, החל מבעיות איטרטיביות פשוטות ועד לבעיות מעקב לאחור מסובכות. במדריך זה, בדקנו את השימוש בשפת Python ליצירת שיטת החיפוש הבינארי הרקורסיבי.