مقدمة في خوارزمية البحث الخطي: مقدمة وميزات [مع أمثلة]

ما هو البحث؟

البحث هو عملية العثور على عنصر معين في قائمة العناصر. يساعد في البحث عن سجل معين. لذلك ، فهي تقنية لتحديد مكان عنصر معين. يعتمد نجاح عملية البحث على ما إذا كان العنصر المراد البحث عنه قد تم تحديده أم لا.

تسمح بنية البيانات بالبحث عن البيانات من خلال طريقتين.

1. البحث الخطي أو البحث المتسلسل
2. بحث ثنائي

البحث الخطي

خوارزميات البحث الخطي هي نوع من الخوارزمية للبحث المتسلسل عن البيانات. تجد هذه الخوارزمية عنصرًا معينًا مع تعقيد O (n). يتم تطبيقه على مجموعة من العناصر. يتم البحث في كل عنصر من عناصر البيانات بشكل تسلسلي ، ويتم إرجاعه إذا كان يتطابق مع العنصر الذي تم البحث عنه. إذا لم يتم العثور على مطابقات ، فسيستمر البحث حتى نهاية البيانات التي تم جمعها. إنها في الأساس تقنية لاستكشاف كل عنصر أثناء اجتياز القائمة. يمكن تطبيق خوارزمية البحث على كل من البيانات المفروزة وغير المصنفة. نادرًا ما يتم استخدام البحث الخطي عمليًا بسبب خيارات البحث الأسرع التي توفرها خوارزميات البحث الأخرى مثل خوارزميات البحث الثنائي وقوائم التجزئة.

خطوات خوارزمية البحث الخطي

• قراءة المستخدم لعنصر البحث.
• يتم ضغط العنصر المراد البحث عنه مع العنصر الأول في القائمة.
• إذا تطابقت العناصر ، فسيتم إنشاء إرجاع.
• إذا لم تتطابق العناصر ، فسيتم مقارنة العنصر المراد البحث عنه بالعنصر الثاني في القائمة.
• تتكرر العملية حتى تتم مطابقة العنصر.

ميزات خوارزميات البحث الخطي

1. يتم تطبيقه عادةً على قائمة صغيرة من البيانات غير المرتبة أو غير المرتبة.
2. يعتمد الوقت خطيًا على عدد العناصر ، وبالتالي يكون له تعقيد زمني إذا كان O (n).
3. التنفيذ بسيط للغاية.

خوارزميات البحث الخطي

تستمر طريقة التكرار المستمر ما لم يتم العثور على العنصر

• الخوارزمية Seqnl_Search (قائمة ، عنصر)
• قبل: قائمة! = ؛
• Post: إرجاع فهرس العنصر إذا وجد ، وإلا: 1
• الفهرس <- fi
• بينما الفهرس <list.Cnt و list [index]! = العنصر // cnt: متغير العداد
• الفهرس <- الفهرس + 1
• تنتهي حين
• إذا كان الفهرس <list.Cnt و list [index] = عنصر
• مؤشر العودة
• إنهاء إذا
• العودة: 1
• نهاية Seqnl_Search

مثال على البحث الخطي

المشكلة: إعطاء مصفوفة arr [] لعناصر n ، اكتب دالة للبحث عن عنصر معين x في arr [].

الشكل 1: مثال على رمز يوضح تنفيذ خوارزمية البحث الخطي

مصدر

يمكن استخدام خوارزميات البحث الخطي في العديد من لغات البرمجة.

1. البحث الخطي في بايثون

الشكل 2: مثال على رمز يظهر خوارزمية بحث خطية بلغة بايثون

مصدر

الإخراج: العنصر موجود في الفهرس 3

2. البحث الخطي في C

الشكل 3: مثال على رمز يظهر خوارزمية بحث خطي بلغة C.

مصدر

الإخراج : العنصر موجود في الفهرس 3

3. البحث الخطي في هيكل البيانات

الكود الزائف لمشكلة البحث الخطي في بنية البيانات هو

الشكل 4: الكود الكاذب لخوارزمية البحث الخطي

مصدر

بحث ثنائي

البحث الثنائي هو خوارزمية للبحث عن العناصر في مجموعة من العناصر. بالمقارنة مع خوارزمية البحث الخطي ، يتم تطبيق خوارزمية البحث الثنائي على قائمة البيانات التي تم فرزها.

تتضمن خوارزمية البحث الثنائي الخطوات التالية

• مقارنة العنصر المراد البحث عنه مع العنصر من منتصف القائمة أو المصفوفة.
• إذا تطابق العنصر مع عنصر من القائمة ، فإنه يُرجع فهرس العنصر الأوسط.
• إذا لم يتم إرجاع أي تطابق ، يتم التحقق مما إذا كان العنصر أكبر من العنصر الموجود في المنتصف أو أقل منه.
• بالنسبة للعنصر ذي القيمة الأكبر من العنصر الأوسط ، يتم البحث على الجانب الأيمن من المصفوفة.
• وبالمثل ، إذا كان العنصر أقل قيمة من العنصر الأوسط ، فسيتم البحث في الجانب الأيسر من القائمة.

لذلك ، يتم تطبيق البحث الثنائي بشكل أفضل عندما تحتوي البيانات على عدد كبير من عناصر قضيب بطريقة مرتبة. هذا يجعل من الضروري لخوارزمية البحث أن يتم فرز القائمة / المصفوفة.

ميزات البحث الثنائي

• تعد خوارزمية البحث الثنائي مفيدة في البحث عن عدد كبير من العناصر في المصفوفة.
• تحتوي خوارزمية البحث الثنائي على تعقيد زمني لـ O (تسجيل الدخول).
• تنفيذ خوارزمية البحث الثنائي بسيط.

خوارزمية البحث الثنائي

• الخوارزمية Binary_Search (قائمة ، عنصر)
• اضبط L على 0 و R على n: 1
• إذا كان L> R ، فسيتم إنهاء Binary_Search على أنه غير ناجح
• آخر
• اضبط m (الموضع في منتصف العنصر) على أرضية (L + R) / 2
• إذا كان Am <T ، فاضبط L على m + 1 وانتقل إلى الخطوة 3
• إذا كان Am> T ، فاضبط R على m: 1 وانتقل إلى الخطوة 3
• الآن ، Am = T ،
• تم البحث العودة (م)

خاتمة

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

إذا كنت مهتمًا بعلوم البيانات ، فيجب عليك التحقق من IIIT-B و upGrad's Executive PG Program in Data Science الذي تم تصميمه بعناية للمهنيين العاملين ويقدم العديد من دراسات الحالة وورش العمل العملية والإرشاد الفردي و أكثر بكثير.