الاختلاف الرئيسي بين البحث الخطي والبحث الثنائي هو أن البحث الثنائي يستغرق وقتًا أقل للبحث عن عنصر من قائمة العناصر التي تم فرزها. لذلك يستنتج أن كفاءة أسلوب البحث الثنائي أكبر من البحث الخطي.
هناك فرق آخر بين الاثنين هو أن هناك شرطًا أساسيًا للبحث الثنائي ، أي أنه يجب فرز العناصر أثناء البحث الخطي ، فلا يوجد مثل هذا الشرط المسبق. على الرغم من استخدام كل من أساليب البحث تقنيات مختلفة والتي نوقشت أدناه.
رسم بياني للمقارنة
| أساس للمقارنة | بحث خطي | بحث ثنائي |
|---|---|---|
| تعقيد الوقت | على) | O (log 2 N) |
| أفضل حالة الوقت | فيرست إليمنت أو (1) | سنتر إليمنت أو (1) |
| شرط أساسي لصفيف | لا حاجة | يجب أن يكون الترتيب في ترتيب فرز |
| أسوأ حالة لعدد N من العناصر | مطلوب N المقارنات | يمكن الاستنتاج بعد المقارنات سجل 2 N فقط |
| يمكن تنفيذها على | المصفوفة والقائمة المرتبطة | لا يمكن تنفيذها مباشرة على القائمة المرتبطة |
| أدخل العملية | إدراجها بسهولة في نهاية القائمة | يتطلب معالجة لإدراجها في مكانها الصحيح للحفاظ على قائمة مرتبة. |
| نوع الخوارزمية | تكراري في الطبيعة | تقسيم وقهر الطبيعة |
| فائدة | سهل الاستخدام وليس هناك حاجة لأي عناصر مرتبة. | وينبغي تنظيم أي خوارزمية وعناصر صعبة على أي حال في النظام. |
| أسطر من التعليمات البرمجية | أقل | أكثر من |
تعريف البحث الخطي
في البحث الخطي ، يتم استرجاع كل عنصر من الصفيف واحدًا تلو الآخر بترتيب منطقي ويتحقق من ما إذا كان العنصر المطلوب أم لا. يكون البحث غير ناجح إذا تم الوصول إلى جميع العناصر ، ولم يتم العثور على العنصر المطلوب. في أسوأ الحالات ، قد يكون عدد الحالات متوسطة الحجم التي نحتاجها لمسح نصف حجم المصفوفة (n / 2).
لذلك يمكن تعريف البحث الخطي على أنه التقنية التي تجتاز المصفوفة بالتسلسل لتحديد العنصر المحدد. يوضح البرنامج المقدم أدناه البحث عن عنصر في الصفيف باستخدام البحث.
كفاءة البحث الخطي
يحدد وقت الاستهلاك أو عدد المقارنات في البحث في سجل في جدول البحث كفاءة التقنية. إذا كان السجل المرغوب موجودًا في الموضع الأول في جدول البحث ، فيتم إجراء مقارنة واحدة فقط. عندما يكون السجل المرغوب هو السجل الأخير ، يجب إجراء مقارنات. إذا كان السجل موجودًا في مكان ما في جدول البحث ، في المتوسط ، سيكون عدد المقارنات (n + 1/2). أسوأ كفاءة لهذه التقنية هي O (n) تعني ترتيب التنفيذ.
برنامج C للبحث عن عنصر باستخدام تقنية البحث الخطي.
#include #include void main () {int a [100]، n، i، item، loc = -1؛ clrscr ()؛ printf ("\ n أدخل عدد العناصر:")؛ scanf ("٪ d"، & n)؛ printf ("أدخل الأرقام: \ n")؛ لـ (i = 0؛ i <= n-1؛ i ++) {scanf ("٪ d"، & a [i])؛ } printf ("\ n أدخل الرقم المراد البحث عنه:") ؛ scanf ("٪ d" ، والبند) ؛ لـ (i = 0؛ i = 0) {printf ("\ n٪ d موجودة في الموضع٪ d:" ، عنصر ، loc + 1)؛ } آخر {printf ("\ n العنصر غير موجود")؛ } getch ()؛ } تعريف البحث الثنائي
البحث الثنائي هو خوارزمية فعالة للغاية. تستهلك تقنية البحث هذه وقتًا أقل في البحث عن العنصر المعين في أقل مقارنات ممكنة. للقيام بالبحث الثنائي ، أولاً ، يجب علينا فرز عناصر الصفيف.
ويرد المنطق وراء هذه التقنية أدناه:
- أولاً ، ابحث عن العنصر الأوسط للصفيف.
- تتم مقارنة العنصر الأوسط للصفيف بالعنصر المراد البحث عنه.
هناك ثلاث حالات يمكن أن تنشأ:
- إذا كان العنصر هو العنصر المطلوب ، فسيكون البحث ناجحًا.
- عندما يكون العنصر أقل من العنصر المطلوب ، ثم ابحث فقط في النصف الأول من الصفيف.
- إذا كان أكبر من العنصر المطلوب ، ثم ابحث في النصف الثاني من الصفيف.
كرر الخطوات نفسها حتى يتم العثور على عنصر أو عوادم في منطقة البحث. في هذه الخوارزمية ، يتم تقليل مساحة البحث في كل مرة. لذلك ، يكون عدد المقارنات هو الأكثر تسجيلًا (N + 1). وكنتيجة لذلك ، فإنه عبارة عن خوارزمية فعالة عند مقارنتها بالبحث الخطي ، ولكن يجب فرز الصفيف قبل إجراء البحث الثنائي.
برنامج C للعثور على عنصر بتقنية البحث الثنائي.
#include void main () {int i، beg، end، middle، n، search، array [100]؛ printf ("أدخل رقم العنصر \ n") ؛ scanf ( "٪ د"، و ن)؛ printf ("أدخل٪ d numbers \ n"، n)؛ لـ (i = 0؛ i <n؛ i ++) scanf ("٪ d" ، والمصفوفة [i]) ؛ printf ("أدخل الرقم المراد البحث عنه \ n") ؛ scanf ("٪ d" ، والبحث) ؛ التسول = 0؛ نهاية = ن - 1 ؛ middle = (beg + end) / 2؛ while (beg <= end) {if (array [middle] end) printf ("البحث غير ناجح!٪ d غير موجود في القائمة. \ n" ، البحث) ؛ getch ()؛ } الاختلافات الرئيسية بين البحث الخطي والبحث الثنائي
- البحث الخطي تكراري بطبيعته ويستخدم نهجًا تسلسليًا. من ناحية أخرى ، يقوم البحث الثنائي بتطبيق نهج التقسيم والقهر.
- وقت تعقيد البحث الخطي هو O (N) بينما البحث الثنائي له O (log 2 N).
- أفضل وقت في البحث الخطي هو العنصر الأول أي O (1). في مقابل ، في البحث الثنائي ، يكون العنصر المتوسط ، أي ، O (1).
- في البحث الخطي ، أسوأ حالة للبحث عن عنصر هو N عدد المقارنة. في المقابل ، فإنه هو سجل 2 N عدد من المقارنة للبحث الثنائي.
- يمكن تنفيذ البحث الخطي في مصفوفة وكذلك في قائمة مرتبطة بينما لا يمكن تنفيذ البحث الثنائي مباشرة على القائمة المرتبطة.
- كما نعلم أن البحث الثنائي يتطلب مصفوفة مرتبة وهذا هو السبب يتطلب معالجة لإدراجها في مكانها الصحيح للحفاظ على قائمة مرتبة. على النقيض ، لا يتطلب البحث الخطي عناصر مصنفة ، بحيث يتم إدراج العناصر بسهولة في نهاية القائمة.
- البحث الخطي سهل الاستخدام ، وليست هناك حاجة لأي عناصر مرتبة. من ناحية أخرى ، فإن خوارزمية البحث الثنائي غير دقيقة ، ويتم ترتيب العناصر بالضرورة بالترتيب.
استنتاج
يمكن أن تكون خوارزميات البحث الخطية والثنائية مفيدة بناءً على التطبيق. عندما يكون المصفوفة هي بنية البيانات ويتم ترتيب العناصر بترتيب تم فرزها ، يُفضل البحث الثنائي للبحث السريع . إذا كانت القائمة المرتبطة هي بنية البيانات بغض النظر عن كيفية ترتيب العناصر ، يتم اعتماد البحث الخطي نظرًا لعدم توفر التطبيق المباشر لخوارزمية البحث الثنائي.
لا يمكن استخدام خوارزمية البحث الثنائي النموذجية في القائمة المرتبطة لأن القائمة المرتبطة ديناميكية بطبيعتها ولا يُعرف أين تم تعيين العنصر الأوسط بالفعل. وبالتالي ، هناك حاجة لتصميم تباين خوارزمية البحث الثنائي التي يمكن أن تعمل على القائمة المرتبطة أيضًا لأن البحث الثنائي أسرع في التنفيذ من البحث الخطي.
