לדלג לתוכן

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