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