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

מבוא

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

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

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

בואו נבין את הרעיון של חיפוש בינארי.

מושג חיפוש בינארי

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

מיון רשימות מערך

• שיטה רקורסיבית
• שיטה איטרטיבית

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

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

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

בואו נעשה יישום צעד אחר צעד של חיפוש בינארי.

יש לנו רשימה ממוינת של אלמנטים, ואנחנו מחפשים את מיקום האינדקס של 45.

[12, 24, 32, 39, 45, 50, 54]

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

לאחר מכן, אנו מחשבים את הערך של אֶמצַע אלמנט במערך.

 mid = (low+high)/2 Here, the low is 0 and the high is 7. mid = (0+7)/2 mid = 3 (Integer) 

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

אם המספר שאנו מחפשים שווה לאמצע. ואז תחזור בֵּינוֹנִי אחרת עברו להשוואה נוספת.

המספר שיש לחפש גדול מהמספר אֶמצַע מספר, אנו משווים את נ עם האלמנט האמצעי של האלמנטים בצד ימין של בֵּינוֹנִי והגדר נמוך ל נמוך = אמצע + 1.

אחרת, השווה את נ עם ה אלמנט אמצעי של האלמנטים בצד שמאל של בֵּינוֹנִי וקבע גָבוֹהַ ל גבוה = אמצע - 1.

חזור עד שיימצא המספר שאנו מחפשים.

יישם חיפוש בינארי ב- Python

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

בואו נבין את התוכנית הבאה של השיטה האיטרטיבית.

יישום Python

 # Iterative Binary Search Function method Python Implementation # It returns index of n in given list1 if present, # else returns -1 def binary_search(list1, n): low = 0 high = len(list1) - 1 mid = 0 while low <= 1 2 high: # for get integer result mid="(high" + low) check if n is present at list1[mid] n: high="mid" - smaller, compared to the left of else: return element was not in list, -1 initial list1 24, 32, 39, 45, 50, 54] function call n) !="-1:" print('element index', str(result)) list1') < pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 4 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above program -</p> <ul> <li>We have created a function called <strong>binary_search()</strong> function which takes two arguments - a list to sorted and a number to be searched.</li> <li>We have declared two variables to store the lowest and highest values in the list. The low is assigned initial value to 0, <strong>high</strong> to <strong>len(list1)</strong> - 1 and mid as 0.</li> <li>Next, we have declared the <strong>while</strong> loop with the condition that the <strong>lowest</strong> is equal and smaller than the <strong>highest</strong> The while loop will iterate if the number has not been found yet.</li> <li>In the while loop, we find the mid value and compare the index value to the number we are searching for.</li> <li>If the value of the mid-index is smaller than <strong>n</strong> , we increase the mid value by 1 and assign it to The search moves to the left side.</li> <li>Otherwise, decrease the mid value and assign it to the <strong>high</strong> . The search moves to the right side.</li> <li>If the n is equal to the mid value then return <strong>mid</strong> .</li> <li>This will happen until the <strong>low</strong> is equal and smaller than the <strong>high</strong> .</li> <li>If we reach at the end of the function, then the element is not present in the list. We return -1 to the calling function.</li> </ul> <p>Let&apos;s understand the recursive method of binary search.</p> <h2>Recursive Binary Search</h2> <p>The recursion method can be used in the binary search. In this, we will define a recursive function that keeps calling itself until it meets the condition.</p> <p>Let&apos;s understand the above program using the recursive function.</p> <h3>Python Program</h3> <pre> # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print(&apos;Element is present at index&apos;, str(res)) else: print(&apos;Element is not present in list1&apos;) </pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 2 </pre> <p> <strong>Explanation</strong> </p> <p>The above program is similar to the previous program. We declared a recursive function and its base condition. The condition is the lowest value is smaller or equal to the highest value.</p> <ul> <li>We calculate the middle number as in the last program.</li> <li>We have used the <strong>if</strong> statement to proceed with the binary search.</li> <li>If the middle value equal to the number that we are looking for, the middle value is returned.</li> <li>If the middle value is less than the value, we are looking then our recursive function <strong>binary_search()</strong> again and increase the mid value by one and assign to low.</li> <li>If the middle value is greater than the value we are looking then our recursive function <strong>binary_search()</strong> again and decrease the mid value by one and assign it to low.</li> </ul> <p>In the last part, we have written our main program. It is the same as the previous program, but the only difference is that we have passed two parameters in the <strong>binary_search()</strong> function.</p> <p>This is because we can&apos;t assign the initial values to the low, high and mid in the recursive function. Every time the recursive is called the value will be reset for those variables. That will give the wrong result.</p> <h2>Complexity</h2> <p>The complexity of the binary search algorithm is <strong>O(1)</strong> for the best case. This happen if the element that element we are looking find in the first comparison. The <strong>O(logn)</strong> is the worst and the average case complexity of the binary search. This depends upon the number of searches are conducted to find the element that we are looking for.</p> <h2>Conclusion</h2> <p>A binary search algorithm is the most efficient and fast way to search an element in the list. It skips the unnecessary comparison. As the name suggests, the search is divided into two parts. It focuses on the side of list, which is close to the number that we are searching.</p> <p>We have discussed both methods to find the index position of the given number.</p> <hr></=>

הֶסבֵּר:

בתוכנית לעיל -

• יצרנו פונקציה בשם חיפוש בינארי() פונקציה שלוקחת שני ארגומנטים - רשימה למיון ומספר לחיפוש.
• הכרזנו על שני משתנים לאחסון הערכים הנמוכים והגבוהים ביותר ברשימה. הערך הנמוך מוקצה ל-0, גָבוֹהַ ל לן(רשימה1) - 1 ואמצע כ-0.
• לאחר מכן, הכרזנו על בזמן לולאה בתנאי שה- הנמוך ביותר שווה וקטן מה- הֲכִי גָבוֹהַ לולאת ה-while תחזור על עצמה אם המספר עדיין לא נמצא.
• בלולאת while, אנו מוצאים את הערך האמצעי ומשווים את ערך האינדקס למספר שאנו מחפשים.
• אם הערך של אמצע המדד קטן מ נ , אנו מגדילים את הערך האמצעי ב-1 ומקצים אותו לחיפוש זז לצד שמאל.
• אחרת, הקטן את הערך האמצעי והקצה אותו ל- גָבוֹהַ . החיפוש עובר לצד ימין.
• אם ה-n שווה לערך האמצע אז החזר בֵּינוֹנִי .
• זה יקרה עד ה נָמוּך שווה וקטן מה- גָבוֹהַ .
• אם נגיע לסוף הפונקציה, אז האלמנט אינו קיים ברשימה. נחזיר -1 לפונקציה הקוראת.

בואו נבין את השיטה הרקורסיבית של חיפוש בינארי.

חיפוש בינארי רקורסיבי

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

בואו נבין את התוכנית לעיל באמצעות הפונקציה הרקורסיבית.

תוכנית פייתון

 # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print('Element is present at index', str(res)) else: print('Element is not present in list1') 

תְפוּקָה:

 Element is present at index 2 

הֶסבֵּר

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

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

בחלק האחרון, כתבנו את התוכנית הראשית שלנו. זה זהה לתוכנית הקודמת, אבל ההבדל היחיד הוא שהעברנו שני פרמטרים ב- חיפוש בינארי() פוּנקצִיָה.

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

מוּרכָּבוּת

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

סיכום

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

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