פייתון/פייתון גרסה 3/חיפוש בינארי

חיפוש בינארי הוא שיטה למציאת איבר ברשימה ממוינת.

אופן פעולה של האלגוריתם

1. האלגוריתם מקבל טווח של החיפוש כלומר שני ערכים בקצוות הרשימה $a,b$.
2. אם טווח החיפוש שמקבל האלגוריתם קטן מאפס - ההרצה תפסק מפני שהרשימה ריקה ותחזיר $-1$
3. נחשב באמצעות ערכי הקצוות את הערך באמצע הרשימה $mid=\frac{a+b}{2}$.
4. נרוץ אל האיבר באמצע הרשימה $lst[mid]$
5. אם הערך המתקבל שווה לערך שרצינו $mid=val$ - התכונה תחזיר את $mid$
6. אם לא - נבחן למקרים.
   • אם $mid<val$ אז כל הערכים לפניו גם הם קטנים מהערך שרצינו (הרי מדובר ברשימה מסודרת) לכן נקרא שוב לאלגוריתם הפעם עם טווח $mid+1,b$
   • אם $mid>val$ אז כל הערכים אחריו גם הם גדולים מהערך שרצינו (הרי מדובר ברשימה מסודרת) לכן נקרא שוב לאלגוריתם הפעם עם טווח $low,mid$

דוגמה

BinarySearch(lst, value, low, high):
    if (high < low):
        return -1 # not found
     mid = ((high + low) // 2)
    
     if (lst[mid] > value):
         return BinarySearch(lst, value, low, mid-1)
     if (lst[mid] < value):
         return BinarySearch(lst, value, mid+1, high)
     else:
         return mid # found

ראי גם

1. חיפוש בינארי - ויקיספר האנגלי