אלגוריתמים: חיפוש
עמוד זה דורש דפדפן עדכני (תומך ב-SharedArrayBuffer). אנא עדכן את Chrome, Edge, Firefox או Safari לגרסה העדכנית ביותר.
מה נעשה
- אלגוריתם הוא רשימה ברורה של צעדים הפותרים בעיה.
- משימה נפוצה מאוד היא חיפוש: למצוא היכן ערך נתון נמצא ברשימה.
- נלמד שני אלגוריתמים: חיפוש ליניארי ו-חיפוש בינארי.
חיפוש ליניארי
- בדוק את הפריטים אחד אחד, מהתחלה ועד הסוף.
- אם מצאת את הערך, החזר את האינדקס (המיקום) שלו.
- אם הגעת לסוף ולא מצאת מעולם, החזר
-1.
English
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
print(linear_search([4, 8, 15, 16], 15))
print(linear_search([4, 8, 15, 16], 99))
מדוע רשימה מסודרת עוזרת
- חיפוש ליניארי עובד על כל רשימה, גם על אחת מבולגנת.
- אך אם הרשימה מסודרת (מקטן לגדול), ניתן להיות מהירים הרבה יותר.
- חיפוש בינארי משתמש בסדר הממוין כדי לדלג על חצי מהרשימה בכל פעם.
חיפוש בינארי
- תסתכל על הפריט באמצע.
- אם זהו המטרה, גימרת.
- אם המטרה קטנה יותר, חפש בחצי הששמאלי; אם גדולה יותר, בחצי השימני. חזור על הפעולה.
English
def binary_search(sorted_lst, target):
low = 0
high = len(sorted_lst) - 1
while low <= high:
mid = (low + high) // 2
if sorted_lst[mid] == target:
return mid
elif sorted_lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9], 7))
print(binary_search([1, 3, 5, 7, 9], 4))
איחוד רעיונות יחד
- חיפוש משלב שלושה בלוקי בנייה שכבר מכיר.
- סידור: ביצוע צעדים בסדר. בחירה:
if/elif/else. - איטרציה: לולאה (
forאוwhile) חוזרת על הבדיקה.
בפסאודוקוד AP CSP
- המבחן כותב לולאה ובדיקה כזו:
FOR EACHמבקר בכל פריט;IFבוחר;REPEAT UNTILלוקח לולאה עד שהמבחן מתקיים.
PROCEDURE contains(list, target)
{
FOR EACH item IN list
{
IF (item = target)
{
RETURN(true)
}
}
RETURN(false)
}
טעויות נפוצות
- חיפוש בינארי דורש רשימה מסודרת.
- חיפוש ליניארי בודק כל פריט בסדר.
כעת תנסו בעצמכם
- לכל משימה נתונים שם של פרוצ'ורה ומה היא צריכה להחזיר.
- לחץ על בדוק תשובה כדי לבדוק את הקוד שלך.
חקור
חיפוש ברשימה
חיפוש בינארי דורש רשימה מוערכת אך מהיר משמעותית יותר מחיפוש ליניארי.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
כתוב linear_search(lst, target). החזר את מדד ה-target ב-lst, או -1 אם הוא אינו קיים. בדוק פריטים אחד אחרי השני.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
כתוב binary_search(sorted_lst, target) לרשימה מוערכת מספר קטן לגדול. החזר את מדד ה-target, או -1. הצב את העין באמצע וחלק את החיפוש למחצה בכל פעם.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
כתוב contains(lst, target) שחוזר True אם target קיים ב-lst, אחרת False. ניתן להשתמש בחיפוש ליניארי ולשוות את התוצאה ל--1.
לחץ על הרץ כדי לראות את התוצא כאן.