البحث الخطي مقابل البحث الثنائي
المحتوى
- المحتويات: الفرق بين البحث الخطي والبحث الثنائي
- رسم بياني للمقارنة
- بحث ثنائي
- الاختلافات الرئيسية
- خاتمة
- فيديو توضيحي
الفرق بين البحث الخطي والبحث الثنائي هو أنه في البحث الخطي يتم فحص كل عنصر ومقارنته ثم فرزه بينما في البحث الثنائي ، يتم تقسيم القائمة المراد فرزها إلى جزأين ثم فرزها. البحث والفرز هما مفهومان رئيسيان في برمجة الكمبيوتر. تُستخدم العديد من الخوارزميات للبحث والفرز ، لكن الخوارزميات الأكثر استخدامًا للبحث والفرز هما البحث الخطي والبحث الثنائي.
الفرق بين البحث الخطي والبحث الثنائي هو العمل والكفاءة لكلتا الخوارزميات. يعتبر البحث الثنائي خوارزمية أكثر فاعلية مقارنة بخوارزمية البحث الخطي. التكرار أو الوقت الذي يستغرقه مقارنة كل قيمة قبل الفرز أقل في البحث الثنائي مقارنة بالبحث الخطي.
يعتبر البحث الخطي خوارزمية معقدة للغاية إذا كنت ترغب في البحث عن رقم في قائمة ما ، قم بمقارنة وتكرار عدد القيم في القائمة في بعض الأحيان. واحدًا تلو الآخر يتم استرداد كل عنصر من عناصر القائمة ومقارنته بالعنصر المجاور. يتم الوصول إلى جميع العناصر والتحقق ثم يتم العثور على العنصر الصحيح. يمكن أن يكون هناك أسوأ حالة إذا كان الرقم الأخير في القائمة هو الرقم الذي سيتم البحث فيه. البحث الخطي هو الطريقة التي يتم بها تتبع المصفوفة وتأسيس العنصر المراد البحث عنه. إذا تحدثنا عن الكفاءة ، فإن الكفاءة هي عدد المرات التي يجب أن يعمل فيها البرنامج للعثور على الرقم. إذا وجدنا العدد الذي نبحث عنه في الموضع الأول ، فيجب إجراء مقارنة واحدة فقط ، ويتم فرز الأشياء ولكن إذا لم يكن الأمر كذلك ، يجب إجراء المقارنات مرارًا وتكرارًا ، وتضيع الذاكرة. في المتوسط ، سيكون عدد المقارنات (n + 1/2). وأسوأ حالة لهذه التقنية هي O (n) لتقف على ترتيب التنفيذ.
بالمقارنة مع البحث الخطي ، فإن البحث الثنائي فعال للغاية. في هذه الطريقة ، يتم تقسيم الصفيف إلى جزئين وبهذه الطريقة يكون عدد المقارنات أقل مقارنةً بالبحث الثنائي. الوقت أقل أيضًا في البحث الثنائي مقارنةً بالبحث الخطي. يعمل البحث الثنائي بالطريقة التي يتم بها العثور على العنصر الأوسط للصفيف ثم مقارنة العنصر الأوسط بجزء واحد من المصفوفة. يمكن أن يكون هناك ثلاثة احتمالات يمكن أن يكون الرقم الأوسط هو الرقم الذي نحتاج إلى إيجاده أو الرقم الذي يكون أقل من الرقم الأوسط أو الرقم أكبر من منتصف الرقم الأوسط. عدد المقارنات على الأكثر سجل (N + 1). يعتبر البحث الثنائي مقارنةً بالبحث الخطي خوارزمية فعالة بالمقارنة بالبحث الخطي ، ولكن يجب تصنيف المجموعة قبل إجراء البحث الثنائي.
المحتويات: الفرق بين البحث الخطي والبحث الثنائي
- رسم بياني للمقارنة
- بحث ثنائي
- الاختلافات الرئيسية
- خاتمة
- فيديو توضيحي
رسم بياني للمقارنة
| أساس | البحث الخطي | بحث ثنائي |
| المعنى | البحث الخطي يتم فحص كل عنصر ومقارنته ثم فرزه | البحث الثنائي يتم تقسيم القائمة التي سيتم فرزها إلى قسمين ثم يتم فرزها.
|
| تعقيد الوقت | التعقيد الزمني للبحث الخطي هو O (N). | التعقيد الزمني للبحث الثنائي هو O (سجل 2 N) |
| نوع الخوارزمية | البحث الخطي هو تكراري. | البحث الثنائي هو فرق تسد. |
| خط الشفرة | في البحث الخطي ، نحتاج إلى كتابة المزيد من الأكواد. | في بحث ثنائي ، نحتاج إلى كتابة كود أقل. |
البحث الخطي
يعتبر البحث الخطي خوارزمية معقدة للغاية إذا كنت ترغب في البحث عن رقم في قائمة ما ، وقارن بين عدد القيم في القائمة وتكرارها في بعض الأحيان. واحدًا تلو الآخر يتم استرداد كل عنصر من عناصر القائمة ومقارنته بالعنصر المجاور. يتم الوصول إلى جميع العناصر والتحقق منها ، ثم يتم العثور على العنصر الصحيح. يمكن أن يكون هناك أسوأ حالة إذا كان الرقم الأخير في القائمة هو الرقم الذي سيتم البحث فيه. البحث الخطي هو الطريقة التي يتم بها تتبع المصفوفة وتأسيس العنصر المراد البحث عنه. إذا تحدثنا عن الكفاءة ، فإن الكفاءة هي عدد المرات التي يجب أن يعمل فيها البرنامج للعثور على الرقم. إذا وجدنا العدد الذي نبحث عنه في الموضع الأول ، فيجب إجراء مقارنة واحدة فقط ، ويتم فرز الأشياء ولكن إذا لم يكن الأمر كذلك ، يجب إجراء المقارنات مرارًا وتكرارًا ، وتضيع الذاكرة. في المتوسط ، سيكون عدد المقارنات (n + 1/2). وأسوأ حالة لكفاءة هذه التقنية هي O (n) لتقف على ترتيب التنفيذ.
بحث ثنائي
بالمقارنة مع البحث الخطي ، يعتبر البحث الثنائي فعالًا جدًا. في هذه الطريقة ، يتم تقسيم الصفيف إلى جزءين وبهذه الطريقة يكون عدد المقارنات أقل مقارنةً بالبحث الثنائي. الوقت أقل أيضًا في البحث الثنائي مقارنةً بالبحث الخطي. يعمل البحث الثنائي بالطريقة التي يتم بها العثور على العنصر الأوسط للصفيف ثم تتم مقارنة العنصر الأوسط بجزء واحد من المصفوفة.
يمكن أن يكون هناك ثلاثة احتمالات يمكن أن يكون الرقم الأوسط هو الرقم الذي نحتاج إلى إيجاده أو الرقم الذي يكون أقل من الرقم الأوسط أو الرقم أكبر من منتصف الرقم الأوسط. عدد المقارنات على الأكثر سجل (N + 1). يعتبر البحث الثنائي مقارنةً بالبحث الخطي خوارزمية فعالة بالمقارنة بالبحث الخطي ، ولكن يجب تصنيف المجموعة قبل إجراء البحث الثنائي.
الاختلافات الرئيسية
- البحث الخطي يتم فحص كل عنصر ومقارنته ثم فرزه في حين يتم البحث الثنائي في قائمة يتم فرزها إلى قسمين ثم يتم فرزها.
- التعقيد الزمني للبحث الخطي هو 0 (N) بينما التعقيد الزمني للبحث الثنائي هو O (log2N).
- البحث الخطي هو تكراري في حين أن البحث الثنائي هو Divide and conquer.
- في البحث الخطي ، نحتاج إلى كتابة المزيد من الأكواد بينما في البحث الثنائي نحتاج إلى كتابة كود أقل.
خاتمة
في هذه المقالة أعلاه ، نرى الفرق الواضح بين البحث الخطي والبحث الثنائي.
