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

تعد القدرة على البحث عن بعض البيانات جانبًا مهمًا من جوانب علوم الكمبيوتر. تُستخدم خوارزميات البحث للبحث عن عنصر معين في مجموعة البيانات.

تعرض الخوارزميات نتيجة منطقية (صواب أو خطأ) لاستعلام البحث. يمكن أيضًا تعديلها لإعطاء الموضع النسبي للقيمة التي تم العثور عليها.

في هذه المقالة ، ستركز الخوارزميات على تحديد ما إذا كانت القيمة موجودة.

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

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

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

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

انظر إلى تطبيق Python أدناه كمثال:

تحديد خطي البحث (قائمتي ، العنصر):

وجدت = خطأ

الفهرس = 0

بينما الفهرس

إذا كانت قائمتي [index] == عنصر:

وجدت = صحيح

آخر:

الفهرس = الفهرس + 1

وجدت العودة

تحليل الخوارزمية

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

سيناريو الحالة المتوسطة في الخوارزمية أعلاه هو n / 2.

متعلق ب: ما هو تدوين Big-O؟

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

من المهم أن تعرف أن الخوارزمية المستخدمة تفترض أنه يتم توفير قائمة عشوائية من العناصر لها. أي أن عناصر القائمة ليست بترتيب معين.

افترض أن العناصر كانت بترتيب معين ، لنقل من الأصغر إلى الأكبر. سيكون من الممكن تحقيق بعض المزايا في الحساب.

خذ مثالاً للبحث عن 19 في القائمة المحددة: [2 ، 5 ، 6 ، 11 ، 15 ، 18 ، 23 ، 27 ، 34]. بعد الوصول إلى 23 ، سيتضح أن العنصر الذي يتم البحث عنه غير موجود في القائمة. لذلك ، لن يكون من المهم الاستمرار في البحث عن باقي عناصر القائمة.

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

لقد رأيت كيف يمكن لقائمة مرتبة أن تقلل من الحساب المطلوب. تستفيد خوارزمية البحث الثنائي أكثر من هذه الكفاءة التي يقدمها وجود قائمة مرتبة.

تبدأ الخوارزمية بأخذ القيمة المتوسطة لقائمة مرتبة والتحقق مما إذا كانت القيمة المطلوبة. إذا لم يكن كذلك ، فسيتم فحص القيمة سواء كانت أقل أو أكبر من القيمة المطلوبة.

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

متعلق ب: ما هو العودية وكيف تستخدمه؟

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

تتكرر هذه العملية حتى يتم العثور على قيمة إذا كانت موجودة.

تطبيق Python أدناه مخصص لخوارزمية البحث الثنائي.

def binarySearch (mylist، item):

منخفض = 0

مرتفع = لين (قائمتي) - 1

وجدت = خطأ

بينما منخفض <= مرتفع وغير موجود:

منتصف = (منخفض + مرتفع) // 2

إذا كانت قائمتي [mid] == عنصر:

وجدت = صحيح

عنصر elif

عالية = منتصف - 1

آخر:

منخفض = منتصف + 1

وجدت العودة

تحليل الخوارزمية

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

بعد المقارنة الأولى ، سيتم ترك عناصر n / 2. بعد الثانية ، ن / 4 عناصر ستترك. بعد الثالث ن / 8.

لاحظ أن عدد العناصر يتناقص إلى النصف حتى يصل إلى n / 2i حيث يمثل i عدد المقارنات. بعد كل هذا التقسيم ، ينتهي بنا الأمر مع عنصر واحد فقط.

هذا يعني:

ن / 2 ط = 1

لذلك ، البحث الثنائي هو O (تسجيل الدخول).

الانتقال إلى الفرز

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

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

كيفية استخدام فرز التحديد

يعتبر فرز الاختيار أمرًا صعبًا بعض الشيء بالنسبة للمبتدئين في الفهم ، ولكنه ليس صعبًا للغاية بمجرد حصولك على تأرجح في الأشياء.

اقرأ التالي

نبذة عن الكاتب