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. · اضغط تشغيل لرؤية المخرجات هنا.