פייתון/פייתון גרסה 3/חיפוש בינארי
< פייתון | פייתון גרסה 3
חיפוש בינארי הוא שיטה למציאת איבר ברשימה ממוינת.
אופן פעולה של האלגוריתם
עריכה- האלגוריתם מקבל טווח של החיפוש כלומר שני ערכים בקצוות הרשימה .
- אם טווח החיפוש שמקבל האלגוריתם קטן מאפס - ההרצה תפסק מפני שהרשימה ריקה ותחזיר
- נחשב באמצעות ערכי הקצוות את הערך באמצע הרשימה .
- נרוץ אל האיבר באמצע הרשימה
- אם הערך המתקבל שווה לערך שרצינו - התכונה תחזיר את
- אם לא - נבחן למקרים.
- אם אז כל הערכים לפניו גם הם קטנים מהערך שרצינו (הרי מדובר ברשימה מסודרת) לכן נקרא שוב לאלגוריתם הפעם עם טווח
- אם אז כל הערכים אחריו גם הם גדולים מהערך שרצינו (הרי מדובר ברשימה מסודרת) לכן נקרא שוב לאלגוריתם הפעם עם טווח
דוגמה
עריכה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