חיפוש
עמוד זה דורש דפדפן עדכני (תומך ב-SharedArrayBuffer). אנא עדכן את Chrome, Edge, Firefox או Safari לגרסה העדכנית ביותר.
חיפוש ברשימה
- חיפוש פירונו למצוא האם ערך קיים ברשימה, ואיפה.
- התשובה המקובלת היא ה-מדד של הערך, או
-1אם הוא חסר. - שתי שיטות קלאסיות הן חיפוש ליניארי וחיפוש בינארי.
חיפוש ליניארי
- בדוק כל פריט בתורו, מהתחלה.
- עצור ברגע שמצאת התאמה.
- זה עובד על כל רשימה, מסודרת או לא.
English
names = ["Sam", "Mia", "Leo"]
target = "Mia"
found = -1
for i in range(len(names)):
if names[i] == target:
found = i
break
print(found)
חיפוש בינארי
- חיפוש בינארי דורש רשימה מסודרת.
- הסתכל בפריט האמצעי. אם זה המטרה, עצור.
- אם המטרה קטנה יותר, חפש בחצי השמאלי; אם גדולה יותר, בחצי הימני.
English
data = [2, 4, 6, 8, 10]
target = 8
low = 0
high = len(data) - 1
found = -1
while low <= high:
mid = (low + high) // 2
if data[mid] == target:
found = mid
break
elif data[mid] < target:
low = mid + 1
else:
high = mid - 1
print(found)
השווה ביניהם
- חיפוש ליניארי עשוי לבדוק כל פריט — איטי לרשימה ארוכה.
- חיפוש בינארי מושלך חצי מהרשימה בכל צעד, ולכן הוא הרבה מהיר יותר.
- אך חיפוש בינארי עובד רק אם הנתונים כבר מסודרים.
בפסאודוקוד קמברידג'
- שים לב ש-
DIVהיא חילוק שלם (ב-Python זהו//). - מערכי קמברידג' רצים בדרך כלל מ-1 עד
n, מספר האלמנטים.LENGTH()מיועד למחרוזות, ולכן הלולאות משתמשות ב-n.
// Linear search — stop at the first match
found ← -1
i ← 1
WHILE i <= n AND found = -1
IF list[i] = target THEN
found ← i
ENDIF
i ← i + 1
ENDWHILE
// Binary search (list must be sorted)
found ← -1
low ← 1
high ← n
WHILE low <= high AND found = -1
MiddleIndex ← (low + high) DIV 2
IF list[MiddleIndex] = target THEN
found ← MiddleIndex
ELSE
IF list[MiddleIndex] < target THEN
low ← MiddleIndex + 1
ELSE
high ← MiddleIndex - 1
ENDIF
ENDIF
ENDWHILE
טעויות נפוצות
- חיפוש בינארי דורש רשימה מסודרת; הוא מחצית את הטווח בכל צעד.
- חיפוש ליניארי עובד על כל רשימה אך הוא איטי יותר.
כעת תנסו בעצמכם
- החזר את ה-מדד של הערך, או
-1כאשר הוא לא נמצא. - לחץ על בדוק תשובה כדי לבדוק את הקוד שלך.
חקור
חיפוש ליניארי לעומת חיפוש בינארי
חיפוש בינארי משניחף את הרשימה בכל צעד — משוויות מעטות הרבה יותר.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
כתוב פונקציה linear_search(items, target) שמחזירה את האינדקס של target ב-items, או -1 אם אינה קיים. בדוק את הפריטים אחד אחד.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
כתוב פונקציה binary_search(items, target) עבור רשימה ממוינת. החזר את האינדקס של target, או -1 אם חסרה. השניחף את הטווח בכל צעד.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
כתוב פונקציה first_negative(items) סורקת את הרשימה ומחזירה את האינדקס של המספר הראשון הקטן מ-0, או -1 אם אין כאלו.
לחץ על הרץ כדי לראות את התוצא כאן.