Searching · חיפוש
Searching a list
- Searching means finding whether a value is in a list, and where.
- The usual answer is the index of the value, or
-1if it is missing. - Two classic methods are linear search and binary search.
חיפוש ברשימה
- חיפוש פירונו למצוא האם ערך קיים ברשימה, ואיפה.
- התשובה המקובלת היא ה-מדד של הערך, או
-1אם הוא חסר. - שתי שיטות קלאסיות הן חיפוש ליניארי וחיפוש בינארי.
Linear search
- Check each item in turn, from the start.
- Stop as soon as you find a match.
- It works on any list, sorted or not.
חיפוש ליניארי
- בדוק כל פריט בתורו, מהתחלה.
- עצור ברגע שמצאת התאמה.
- זה עובד על כל רשימה, מסודרת או לא.
names = ["Sam", "Mia", "Leo"]
target = "Mia"
found = -1
for i in range(len(names)):
if names[i] == target:
found = i
break
print(found)
Binary search
- Binary search needs a sorted list.
- Look at the middle item. If it is the target, stop.
- If the target is smaller, search the left half; if bigger, the right half.
חיפוש בינארי
- חיפוש בינארי דורש רשימה מסודרת.
- הסתכל בפריט האמצעי. אם זה המטרה, עצור.
- אם המטרה קטנה יותר, חפש בחצי השמאלי; אם גדולה יותר, בחצי הימני.
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)
Compare them
- Linear search may check every item — slow for a long list.
- Binary search throws away half the list each step, so it is much faster.
- But binary search only works if the data is already sorted.
השווה ביניהם
- חיפוש ליניארי עשוי לבדוק כל פריט — איטי לרשימה ארוכה.
- חיפוש בינארי מושלך חצי מהרשימה בכל צעד, ולכן הוא הרבה מהיר יותר.
- אך חיפוש בינארי עובד רק אם הנתונים כבר מסודרים.
In Cambridge pseudocode
- Note
DIVis whole-number division (Python's//).
בפסאודוקוד קמברידג'
- שים לב ש-
DIVהיא חילוק שלם (ב-Python זהו//).
// Linear search — stop at the first match
found ← -1
i ← 0
WHILE i < LENGTH(list) AND found = -1
IF list[i] = target THEN
found ← i
ENDIF
i ← i + 1
ENDWHILE
// Binary search (list must be sorted)
found ← -1
low ← 0
high ← LENGTH(list) - 1
WHILE low <= high AND found = -1
mid ← (low + high) DIV 2
IF list[mid] = target THEN
found ← mid
ELSE
IF list[mid] < target THEN
low ← mid + 1
ELSE
high ← mid - 1
ENDIF
ENDIF
ENDWHILE
Common mistakes
- Binary search needs a sorted list; it halves the range each step.
- Linear search works on any list but is slower.
טעויות נפוצות
- חיפוש בינארי דורש רשימה מסודרת; הוא מחצית את הטווח בכל צעד.
- חיפוש ליניארי עובד על כל רשימה אך הוא איטי יותר.
Now you try
- Return the index of the value, or
-1when it is not found. - Press Check answer to test your code.
כעת תנסו בעצמכם
- החזר את ה-מדד של הערך, או
-1כאשר הוא לא נמצא. - לחץ על בדוק תשובה כדי לבדוק את הקוד שלך.
Linear vs binary search · חיפוש ליניארי לעומת חיפוש בינארי
Binary search halves the list each step — far fewer comparisons. · חיפוש בינארי משניחף את הרשימה בכל צעד — משוויות מעטות הרבה יותר.
Write linear_search(items, target) that returns the index of target in items, or -1 if it is not there. Check the items one by one. · כתוב פונקציה linear_search(items, target) שמחזירה את האינדקס של target ב-items, או -1 אם אינה קיים. בדוק את הפריטים אחד אחד.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Write binary_search(items, target) for a sorted list. Return the index of target, or -1 if it is missing. Halve the range each step. · כתוב פונקציה binary_search(items, target) עבור רשימה ממוינת. החזר את האינדקס של target, או -1 אם חסרה. השניחף את הטווח בכל צעד.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Write first_negative(items) that scans the list and returns the index of the first number less than 0, or -1 if there are none. · כתוב פונקציה first_negative(items) סורקת את הרשימה ומחזירה את האינדקס של המספר הראשון הקטן מ-0, או -1 אם אין כאלו.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.