الخوارزميات: البحث
ما سنفعله
- الخوارزمية هي قائمة واضحة من الخطوات تحل مشكلة ما.
- وظيفة شائعة جدًا هي البحث: إيجاد مكان قيمة معينة داخل قائمة.
- سنتعلم خوارزميتين: البحث الخطي والبحث الثنائي.
البحث الخطي
- افحص العناصر واحدًا تلو الآخر، من البداية إلى النهاية.
- إذا وجدت القيمة، أدرج فهرسها (موقعها).
- إذا وصلت إلى النهاية ولم تجدها أبدًا، أدرج
-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))
لماذا تساعد القائمة المرتبة
- يعمل البحث الخطي على أي قائمة، حتى الفوضوية منها.
- لكن إذا كانت القائمة مرتبة (من الأصغر للأكبر)، يمكننا أن نكون أسرع بكثير.
- البحث الثنائي يستخدم الترتيب المرتب لتخطي نصف القائمة في كل مرة.
البحث الثنائي
- انظر إلى العنصر الأوسط.
- إذا كان هو الهدف، فأنت منه.
- إذا كان الهدف أصغر، ابحث في النصف اليسار؛ إذا أكبر، في النصف الأيمن. كرر العملية.
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.
اضغط تشغيل لرؤية المخرجات هنا.