هل البحث الثنائي هو الأسرع؟

2024 مؤلف: Lynn Donovan | [email protected]. آخر تعديل: 2023-12-15 23:43

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

ببساطة ، هل البحث الثنائي أسرع من البحث الخطي؟

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

ثانيًا ، هل البحث الثنائي هو الأفضل؟ إذا تم فرز البيانات بالفعل على المفتاح ، فأنت يبحث ل ، إذن بحث ثنائي بعيد أفضل من الخطي بحث . إعادة التدريج قليلاً ، إذا كان هناك 40000 عنصر في المصفوفة ، بحث ثنائي سيكلف على الأكثر 16 مقارنة ، بينما خطي بحث سيكلف على الأكثر 40 ألف مقارنة ، وفي المتوسط 20 ألف مقارنة.

في هذا الصدد ، ما هي أسرع خوارزمية البحث؟

بحث ثنائي

ما هو الوقت المعقد للبحث الثنائي؟

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