Algorithms: searching · אלגוריתמים: חיפוש
What we'll do
- An algorithm is a clear list of steps that solves a problem.
- A very common job is searching: find where a value is in a list.
- We will learn two algorithms: linear search and binary search.
מה נעשה
- אלגוריתם הוא רשימה ברורה של צעדים הפותרים בעיה.
- משימה נפוצה מאוד היא חיפוש: למצוא היכן ערך נתון נמצא ברשימה.
- נלמד שני אלגוריתמים: חיפוש ליניארי ו-חיפוש בינארי.
Linear search
- Check the items one by one, from start to end.
- If you find the value, return its index (position).
- If you reach the end and never find it, return
-1.
חיפוש ליניארי
- בדוק את הפריטים אחד אחד, מהתחלה ועד הסוף.
- אם מצאת את הערך, החזר את האינדקס (המיקום) שלו.
- אם הגעת לסוף ולא מצאת מעולם, החזר
-1.
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))
Why a sorted list helps
- Linear search works on any list, even a messy one.
- But if the list is sorted (small to big), we can be much faster.
- Binary search uses the sorted order to skip half the list each time.
מדוע רשימה מסודרת עוזרת
- חיפוש ליניארי עובד על כל רשימה, גם על אחת מבולגנת.
- אך אם הרשימה מסודרת (מקטן לגדול), ניתן להיות מהירים הרבה יותר.
- חיפוש בינארי משתמש בסדר הממוין כדי לדלג על חצי מהרשימה בכל פעם.
Binary search
- Look at the middle item.
- If it is the target, you are done.
- If the target is smaller, search the left half; if bigger, the right half. Repeat.
חיפוש בינארי
- תסתכל על הפריט באמצע.
- אם זהו המטרה, גימרת.
- אם המטרה קטנה יותר, חפש בחצי הששמאלי; אם גדולה יותר, בחצי השימני. חזור על הפעולה.
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))
Putting ideas together
- A search combines three building blocks you already know.
- Sequencing: do steps in order. Selection:
if/elif/else. - Iteration: a loop (
fororwhile) repeats the check.
איחוד רעיונות יחד
- חיפוש משלב שלושה בלוקי בנייה שכבר מכיר.
- סידור: ביצוע צעדים בסדר. בחירה:
if/elif/else. - איטרציה: לולאה (
forאוwhile) חוזרת על הבדיקה.
In AP CSP pseudocode
- The exam writes a loop and a check like this.
FOR EACHvisits every item;IFselects;REPEAT UNTILloops until a test is true.
בפסאודוקוד AP CSP
- המבחן כותב לולאה ובדיקה כזו:
FOR EACHמבקר בכל פריט;IFבוחר;REPEAT UNTILלוקח לולאה עד שהמבחן מתקיים.
PROCEDURE contains(list, target)
{
FOR EACH item IN list
{
IF (item = target)
{
RETURN(true)
}
}
RETURN(false)
}
Common mistakes
- Binary search needs a sorted list.
- Linear search checks each item in turn.
טעויות נפוצות
- חיפוש בינארי דורש רשימה מסודרת.
- חיפוש ליניארי בודק כל פריט בסדר.
Now you try
- Each task gives a procedure name and what it must return.
- Press Check answer to test your code.
כעת תנסו בעצמכם
- לכל משימה נתונים שם של פרוצ'ורה ומה היא צריכה להחזיר.
- לחץ על בדוק תשובה כדי לבדוק את הקוד שלך.
Searching a list · חיפוש ברשימה
Binary search needs a sorted list but is far faster than linear. · חיפוש בינארי דורש רשימה מוערכת אך מהיר משמעותית יותר מחיפוש ליניארי.
Write linear_search(lst, target). Return the index of target in lst, or -1 if it is not there. Check items one by one. · כתוב linear_search(lst, target). החזר את מדד ה-target ב-lst, או -1 אם הוא אינו קיים. בדוק פריטים אחד אחרי השני.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Write binary_search(sorted_lst, target) for a list sorted small to big. Return the index of target, or -1. Look at the middle and cut the search in half each time. · כתוב binary_search(sorted_lst, target) לרשימה מוערכת מספר קטן לגדול. החזר את מדד ה-target, או -1. הצב את העין באמצע וחלק את החיפוש למחצה בכל פעם.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Write contains(lst, target) that returns True if target is in lst, else False. You may reuse linear search and compare the result to -1. · כתוב contains(lst, target) שחוזר True אם target קיים ב-lst, אחרת False. ניתן להשתמש בחיפוש ליניארי ולשוות את התוצאה ל--1.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.