قبل فهم الاختلافات بين البحث الخطي والبحث الثنائي، يجب علينا أولاً معرفة البحث الخطي والبحث الثنائي بشكل منفصل.

ما هو البحث الخطي؟

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

دعونا نفكر في مثال بسيط.

لنفترض أن لدينا مجموعة من 10 عناصر كما هو موضح في الشكل أدناه:

يوضح الشكل أعلاه مصفوفة من أنواع الأحرف تحتوي على 10 قيم. إذا أردنا البحث عن 'E'، فإن البحث يبدأ من الرقم 0^ذالعنصر ويقوم بمسح كل عنصر حتى يتم العثور على العنصر، أي 'E'. لا يمكننا القفز مباشرة من الصفر^ذعنصر إلى 4^ذالعنصر، أي يتم فحص كل عنصر واحدًا تلو الآخر حتى لا يتم العثور على العنصر.

تعقيد البحث الخطي

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

ما هو البحث الثنائي؟

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

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

هناك ثلاث حالات تستخدم في البحث الثنائي:

الحالة 1: البيانات

الحالة 2: البيانات>أ[منتصف] ثم يمين=منتصف-1

الحالة 3: البيانات = a[mid] // تم العثور على العنصر

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

دعونا نفهم عمل البحث الثنائي من خلال مثال.

لنفترض أن لدينا مصفوفة بحجم 10 مفهرسة من 0 إلى 9 كما هو موضح في الشكل أدناه:

نريد البحث عن 70 عنصرًا من المصفوفة أعلاه.

الخطوة 1: أولاً، نقوم بحساب العنصر الأوسط في المصفوفة. نحن نعتبر متغيرين، أي اليسار واليمين. في البداية، اليسار = 0 واليمين = 9 كما هو موضح في الشكل أدناه:

يمكن حساب قيمة العنصر الأوسط على النحو التالي:

لذلك، mid = 4 وa[mid] = 50. العنصر المطلوب البحث عنه هو 70، لذا فإن a[mid] لا يساوي البيانات. الحالة 2 راضية، أي البيانات> أ [منتصف].

الخطوة 2: كبيانات>a[mid]، يتم زيادة قيمة اليسار بمقدار mid+1، أي left=mid+1. قيمة المنتصف هي 4، وبالتالي تصبح قيمة اليسار 5. الآن، أصبح لدينا مصفوفة فرعية كما هو موضح في الشكل أدناه:

الآن مرة أخرى، يتم حساب القيمة المتوسطة باستخدام الصيغة أعلاه، وتصبح قيمة المنتصف 7. الآن، يمكن تمثيل المنتصف على النحو التالي:

في الشكل أعلاه، يمكننا ملاحظة أن a[mid]>data، لذا مرة أخرى، سيتم حساب قيمة mid في الخطوة التالية.

الخطوه 3: باعتبارها بيانات [mid]>، يتم تقليل قيمة الحق بمقدار منتصف 1. قيمة المنتصف هي 7، وبالتالي تصبح قيمة اليمين 6. يمكن تمثيل المصفوفة على النحو التالي:

سيتم حساب قيمة منتصف مرة أخرى. قيم اليسار واليمين هي 5 و 6 على التوالي. وبالتالي فإن قيمة mid هي 5. والآن يمكن تمثيل الوسط في مصفوفة كما هو موضح أدناه:

في الشكل أعلاه، يمكننا أن نلاحظ أن [منتصف]

الخطوة 4: ك[منتصف]

الآن يتم حساب قيمة المنتصف مرة أخرى باستخدام الصيغة التي ناقشناها بالفعل. قيمتي اليسار واليمين هي 6 و 6 على التوالي، وبالتالي تصبح قيمة المنتصف 6 كما هو موضح في الشكل أدناه:

يمكننا أن نلاحظ في الشكل أعلاه أن a[mid]=data. ولذلك، اكتمل البحث، وتم العثور على العنصر بنجاح.

الاختلافات بين البحث الخطي والبحث الثنائي

فيما يلي الاختلافات بين البحث الخطي والبحث الثنائي:

وصف

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

العمل على كلا البحثين

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

تطبيق

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

تعقيد

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

العناصر مرتبة

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

يقترب

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

مجموعة البيانات

التكرار من خلال خريطة Java

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

سرعة

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

أبعاد

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

كفاءة

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

دعونا نلقي نظرة على الاختلافات في شكل جدول.