خوارزميات البحث
| English | العربية |
|---|---|
| Searching/ˈsɜːtʃɪŋ/ | البحث |
| linear search/ˈlɪnɪə sɜːtʃ/ | البحث الخطي |
| binary search/ˈbaɪnəri sɜːtʃ/ | البحث الثنائي |
| sorted/ˈsɔːtɪd/ | مرتبة |
إيجاد قيمة
- البحث يعني تحديد قيمة هدف في مجموعة ما.
- خوارزمتان قياسية: البحث الخطي والبحث الثنائي.
- كلاهما يُرجع الفهرس الذي يقع فيه الهدف — أو إشارة "لم يتم العثور" (غالباً
-1). - أيهما تستخدم يعتمد على ما إذا كانت البيانات مرتبة.
البحث الخطي
- تحقق من كل عنصر من البداية، واحداً تلو الآخر، حتى تجد الهدف.
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;- يعمل على أي مصفوفة — مرتبة أم لا.
- أسوأ حالة: ينظر إلى كل العناصر (
nفحوصات).
البحث الثنائي
- يحتاج مصفوفة مرتبة. انظر إلى العنصر الوسطى في كل مرة.
- إذا كانت الوسطى هي الهدف، انتهى. إذا كان الهدف أصغر، ابحث في النصف الأيسر؛ إذا أكبر، النصف الأيمن.
- كل خطوة تُضعّف النطاق المتبقي للبحث.
- أسرع بكثير على المصفوفات المرتبة الكبيرة — حوالي
log₂ nفحوصات، بدلاً منn.
لماذا البحث الثنائي سريع
- بحث خطي لمليون عنصر: حتى مليون فحص.
- بحث ثنائي لمليون عنصر مرتبة: حوالي 20 فحصاً.
- الشرط: يجب أن تكون المصفوفة مرتبة بالفعل.
- التقسيم المتكرر للنصف هو الفكرة الكبرى وراء
O(log n).
البحث الثنائي يعمل فقط على مصفوفة مُرتبة — تشغيله على بيانات غير مرتبة يعطي إجابات خاطئة. كما أنه يقارن بالوسطى ويتخلص من نصف النطاق في كل خطوة؛ بينما المقارنة الخطية تبدأ من البداية وت丢弃 عنصراً واحداً فقط. إذا كنت غير متأكد من أن البيانات مرتبة، يجب عليك استخدام البحث الخطي (أو ترتيبها أولاً).
بحث ثنائي لرقم 7 في [1, 3, 5, 7, 9]:
- الوسطى هي
5(الفهرس 2). 7 > 5، لذا ابحث في النصف الأيمن. - النصف الأيمن هو
[7, 9]؛ الوسطى هي7. تم العثور عليه عند الفهرس 3. - فحوصتان بدلاً من أربع — النصف انخفض في كل مرة.
البحث الخطي يفحص العناصر من البداية (يعمل على أي مصفوفة، حتى n فحوصات). البحث الثنائي يحتاج مصفوفة مرتبة، يقارن بالوسطى، ويُضعّف نطاق البحث في كل خطوة (حوالي log₂ n فحوصات). كلاهما يُرجع الفهرس الذي تم العثور عليه، أو إشارة "لم يتم العثور" مثل -1.
البحث الخطي مقابل الثنائي
يقسم البحث الثنائي النطاق المرتب إلى نصفين في كل خطوة.
البحث الخطي...
الخطي = من البداية إلى النهاية؛ يعمل على أي مصفوفة.
يتطلب البحث الثنائي أن تكون المصفوفة...
يعمل البحث الثنائي فقط على بيانات مرتبة.
كل خطوة من خطوات البحث الثنائي...
يقارن بالمنتصف ويحتفظ بنصف واحد.
البحث الثنائي في [1,3,5,7,9] للرقم 7: كم عدد المقارنات (في المنتصف كل مرة)؟
قارن بـ 5، ثم بـ 7 — مقارنتان.
يعطي البحث الثنائي نتائج صحيحة على مصفوفة غير مُرتَبة.
يعتمد على الترتيب؛ البيانات غير المرتبة تعطله.
طابق كل بحث بخصائصه.
الخطي عام لكنه أبطأ؛ الثنائي سريع لكنه يحتاج ترتيباً.