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