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

 مفهوم خوارزمية البحث الخطي linear Search:

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

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

والآن سننظر لمثال يبين لنا كيفية عمل خوارزمية البحث الخطي على أنها متعلقة بعلوم الحاسوب، بدلاً من دليل الهاتف، لدينا مجموعة الأعداد الصحيحة في مصفوفة: ( 9, -1, 7, 10, 3)، دعونا نبحث عن الرقم (7)، نبدأ من البداية ونتحقق من العنصر الأول في المصفوفة. هل هو (7)؟ لا ليس كذلك، هل هو العنصر التالي؟ ليس كذلك أيضًا، هل هو العنصر التالي؟ نعم!، هذه هي الفكرة من البحث الخطي؛ نمر بكل عنصر بالترتيب حتى نجد القيمة الصحيحة.

حساب تعقيد الوقت لخوارزمية البحث الخطي time complexity:

البحث الخطي في أفضل الأحوال (best case) “O(1)”، وفي أسوأ الأحوال (worst case) “O(n)”، وفي المتوسط “O(n)”. إذا لم يتم ترتيب البيانات التي يتم البحث عنها، فهذه الخوارزمية تعد فعالة نسبيًا، ومع ذلك، إذا تم فرز البيانات التي يتم البحث عنها، فيمكننا استخدام خوارزميات أفضل بكثير.

مشاكل برمجية حول خوارزمية البحث الخطي وحلولها:

مشكلة (1):

لديك مصفوفة حجمها (N) تتكون من أعداد صحيحة، وقد تم إعطاؤك عنصر (M)، تحتاج إلى البحث عن مكان لآخر ظهور للعنصر (M) في المصفوفة وطباعته إذا كان موجودًا فيها، وإذا لم يكن موجوداً اطبع (-1).

المدخلات:

يتكون السطر الأول من عددين صحيحين (N) للدلالة على حجم المصفوفة، حيث (N ≤ 100)، و(M) العنصر المراد البحث عنه في المصفوفة على التوالي، يحتوي السطر التالي على أعداد صحيحة عددها (N) مفصولة بمسافة تشير إلى عناصر المصفوفة.

المخرجات:

اطبع عددًا صحيحًا واحدًا يشير إلى مكان (index) آخر تواجد للعدد الصحيح (M) في المصفوفة إذا كان موجودًا، وإلا اطبع (-1).

مثال:

المدخلات:

5 1
1 2 3 4 1

المخرجات:

4

الحل: (مقترح)

مشكلة(2):

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

المدخلات:

يحتوي السطر الأول من الإدخال على عدد صحيح (n) عدد البطاقات في المجموعة. حيث أن (n ≤ 100)، (n) دائما زوجي، ويحتوي السطر الثاني على تسلسل عدده (n) من الأعداد الصحيحة الموجبة (1 ≤ ai)، حيث أن (ai) هو الرقم المكتوب على الكرة (i).

المخرجات:

طباعة (n/2) زوج من الأعداد الصحيحة، الزوج (i) يشير إلى الكرات التي يجب أن تعطى للاعب (i)، يجب منح كل كرة إلى لاعب واحد بالضبط. يتم ترقيم الكرات بالترتيب الذي تظهر به في الإدخال، (سيكون هناك دائما الحل موجود).

مثال:

المدخلات:

6
1 5 7 4 4 3

المخرجات:

1 3
6 2
4 5

الحل: (مقترح)