البحث الخطي والثنائي عن العناصر في المصفوفة

البحث عن المصفوفة الخطية غالبًا ما تحتاج إلى العثور على قيمة معينة في مصفوفة أو تقرير بأنها غير موجودة. للقيام بذلك ، تحتاج إلى النظر في جميع عناصر المصفوفة من الأول إلى الأخير. بمجرد العثور على عنصر يساوي القيمة المحددة X ، يجب أن ينتهي البحث ويجب عرض النتيجة. تسمى هذه الخوارزمية الخطية.

يتم استخدام خوارزمية خطية للعثور على الحد الأقصى (الأدنى) لعنصر المصفوفة. هذه أيضًا خوارزمية بحث. ولكن هنا نحن مضطرون للذهاب إلى نهاية المصفوفة ، لأن من الضروري مقارنة جميع العناصر بالقيمة القصوى (الدنيا) الحالية وإذا كان العنصر الحالي أكبر (أقل) من القيمة القصوى (الدنيا) ، فاستبدل القيمة القصوى (الدنيا). & nbsp ؛
نبسب ؛

بحث ثنائي

البحث الثنائي (أو الثنائي) هو خوارزمية بحث فعالة وأسرع من البحث الخطي. على سبيل المثال ، بالنسبة لمصفوفة من 1024 عنصرًا ، فإن البحث الخطي في أسوأ الحالات (عندما لا يكون العنصر المطلوب في المصفوفة) سيعالج جميع العناصر البالغ عددها 1024 ، ولكن يكفي معالجة 10 عناصر ببحث ثنائي. يتم تحقيق هذه النتيجة بسبب حقيقة أنه بعد الخطوة الأولى من الحلقة ، تضيق منطقة البحث إلى 512 عنصرًا ، بعد الثانية & ndash ؛ ما يصل إلى 256 إلخ.

& nbsp؛

تتمثل عيوب هذه الخوارزمية في متطلبات ترتيب البيانات ، فضلاً عن القدرة على الوصول إلى أي عنصر بيانات في وقت ثابت (بغض النظر عن كمية البيانات). لذلك ، لا يمكن أن تعمل الخوارزمية على المصفوفات غير المرتبة.
نبسب ؛

الخوارزمية

1. حدد العنصر الأوسط A [c] والمقارنة بـ X .
2. إذا كان X = A [c] ثم تم العثور على (توقف).
3. إذا كان X & lt؛ أ [ج] ، ابحث أكثر في الشوط الأول.
4. إذا كان X & gt؛ & nbsp؛ A [c] ، فابحث في النصف الثاني.
   نبسب ؛

التنفيذ L = 0 ؛ R = N ؛ // الجزء الأولي بينما (L & lt ؛ R - 1) { ج = (L + R) / 2 ؛ // وجد الوسط إذا (X & lt؛ A [c]) // ضغط المقطع ص = ج ؛ آخر L = ج ؛ } إذا (A [L] == X) كوت & lt؛ & lt؛ & quot؛ ا & quot؛ & lt؛ & lt؛ L & lt؛ & lt؛ & quot؛] = & quot؛ & lt؛ & lt؛ العاشر ؛ آخر كوت & lt؛ & lt؛ & quot؛ غير موجود & quot ؛؛

حيث:
A - مصفوفة المصدر ،
N - حجم المصفوفة ،
X - الرقم الذي تم البحث عنه ،

تطبيقات أخرى ممكنة.
على سبيل المثال ، استخدام مخرج مبكر من الحلقة L = 0 ؛ R = N - 1 ؛ بينما (R & GT ؛ = L) { ج = (L + R) / 2 ؛ إذا (X == A [c]) { ن س = ج ؛ استراحة؛ } إذا (X & lt؛ A [ج]) R = منتصف - 1 ؛ إذا (X & gt؛ A [c]) L = mid + 1 ؛ } إذا (nX & lt؛ 0) كوت & lt؛ & lt؛ & quot؛ غير موجود & quot ؛؛ آخر كوت & lt؛ & lt؛ & quot؛ ا & quot؛ & lt؛ & lt؛ nX & lt؛ & lt؛ & quot؛] = & quot؛ & lt؛ & lt؛ X ؛

مقارنة خوارزميات البحث الخطي والثنائي بعدد المقارنات نبسب ؛

أمثلة <الجسم>

#	خط البحث	بحث ثنائي
2	2	2
16	16	5
1024	1024	11
1048576	1048576	21

ميزة التصنيف الثنائي هي أنه أسرع.
سلبيات - مطلوب مصفوفة مرتبة مسبقًا.

نبسب ؛