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

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

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

עריכה
  1. האלגוריתם מקבל טווח של החיפוש כלומר שני ערכים בקצוות הרשימה  .
  2. אם טווח החיפוש שמקבל האלגוריתם קטן מאפס - ההרצה תפסק מפני שהרשימה ריקה ותחזיר  
  3. נחשב באמצעות ערכי הקצוות את הערך באמצע הרשימה  .
  4. נרוץ אל האיבר באמצע הרשימה  
  5. אם הערך המתקבל שווה לערך שרצינו   - התכונה תחזיר את  
  6. אם לא - נבחן למקרים.
    • אם   אז כל הערכים לפניו גם הם קטנים מהערך שרצינו (הרי מדובר ברשימה מסודרת) לכן נקרא שוב לאלגוריתם הפעם עם טווח  
    • אם   אז כל הערכים אחריו גם הם גדולים מהערך שרצינו (הרי מדובר ברשימה מסודרת) לכן נקרא שוב לאלגוריתם הפעם עם טווח  

דוגמה

עריכה
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. חיפוש בינארי - ויקיספר האנגלי