المحتوى

• رسم بياني للمقارنة
• تعريف البحث الخطي
• تعريف البحث الثنائي
• استنتاج

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

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

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

1. رسم بياني للمقارنة
2. فريف
3. الاختلافات الرئيسية
4. استنتاج

رسم بياني للمقارنة

أساس للمقارنة	البحث الخطي	بحث ثنائي
تعقيد الوقت	على)	O (سجل 2 N)
أفضل وقت القضية	العنصر الأول يا (1)	عنصر مركز يا (1)
شرط أساسي لمجموعة	لا حاجة	يجب أن تكون المصفوفة مرتبة
الحالة الأسوأ لعدد N من العناصر	N مقارنات مطلوبة	يمكن أن تختتم بعد تسجيل فقط2مقارنات N
يمكن تنفيذها على	صفيف والقائمة المرتبطة	لا يمكن تنفيذها مباشرة على قائمة مرتبطة
إدراج العملية	إدراج بسهولة في نهاية القائمة	تتطلب المعالجة لإدراجها في مكانها الصحيح للحفاظ على قائمة مرتبة.
نوع الخوارزمية	تكراري في الطبيعة	فرق تسد في الطبيعة
فائدة	سهل الاستخدام ولا حاجة لأي عناصر مطلوبة.	على أي حال خوارزمية صعبة والعناصر ينبغي تنظيمها في النظام.
أسطر من التعليمات البرمجية	أقل	أكثر من

تعريف البحث الخطي

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

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

نجاعة البحث الخطي

يحدد استهلاك الوقت أو عدد المقارنات التي تم إجراؤها في البحث عن سجل في جدول البحث كفاءة هذه التقنية. إذا كان السجل المطلوب موجودًا في الموضع الأول من جدول البحث ، فيتم إجراء مقارنة واحدة فقط. عندما يكون السجل المطلوب هو السجل الأخير ، فيجب إجراء مقارنات n. إذا كان السجل سيقدم في مكان ما في جدول البحث ، في المتوسط ​​، فسيكون عدد المقارنات (n + 1/2). أسوأ حالة لهذه التقنية هي O (n) لتقف على ترتيب التنفيذ.

برنامج C للبحث عن عنصر باستخدام تقنية البحث الخطي.

#تضمن #تضمن void main () {int a، n، i، item، loc = -1؛ clrscr ()؛ f (" n أدخل رقم العنصر:") ؛ scanf ("٪ d"، & n)؛ f ("أدخل الأرقام: n") ؛ عن (i = 0؛ i <= n-1؛ i ++) {scanf ("٪ d"، & a)؛ } f (" n أدخل الرقم الذي سيتم البحث فيه:")؛ scanf ("٪ d"، & item)؛ لـ (i = 0 ؛ i <= n-1 ؛ i ++) {if (item == a) {loc = i؛ استراحة؛ }} إذا تم العثور على (loc> = 0) {f (" n٪ d في الموضع٪ d:"، item، loc + 1)؛ } {f (" n العنصر غير موجود")؛ } getch ()؛ }

تعريف البحث الثنائي

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

ويرد المنطق وراء هذه التقنية أدناه:

• أولاً ، ابحث عن العنصر الأوسط للصفيف.
• تتم مقارنة العنصر الأوسط للصفيف بالعنصر المطلوب البحث عنه.

هناك ثلاث حالات يمكن أن تنشأ:

1. إذا كان العنصر هو العنصر المطلوب ، فسيكون البحث ناجحًا.
2. عندما يكون العنصر أقل من العنصر المطلوب ، ابحث في النصف الأول فقط من الصفيف.
3. إذا كان أكبر من العنصر المطلوب ، فابحث في النصف الثاني من الصفيف.

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

برنامج C للعثور على عنصر مع تقنية البحث الثنائية.

#تضمن void main () {int i، beg، end، middle، n، search، array؛ f ("أدخل رقم العنصر n") ؛ scanf ( "٪ د"، و ن)؛ f ("أدخل الأرقام٪ d n" ، n) ؛ من أجل (i = 0؛ i <n؛ i ++) scanf ("٪ d"، & array)؛ f ("أدخل الرقم المطلوب البحث عنه n") ؛ scanf ("٪ d" ، والبحث) ؛ التسول = 0 ؛ نهاية = ن - 1 ؛ الأوسط = (التسول + النهاية) / 2 ؛ بينما (beg <= end) {if (array <search) beg = middle + 1؛ else if (array == search) {f ("البحث ناجح. n٪ d تم العثور عليه في الموقع٪ d. n" ، search ، middle + 1)؛ استراحة؛ } نهاية أخرى = منتصف - 1 ؛ الأوسط = (التسول + النهاية) / 2 ؛ } إذا (beg> end) f ("البحث غير ناجح!٪ d غير موجود في القائمة. n" ، بحث) ؛ getch ()؛ }

1. البحث الخطي هو تكراري بطبيعته ويستخدم نهج متسلسل. من ناحية أخرى ، فإن البحث الثنائي ينفذ مقاربة الانقسام والقهر.
2. التعقيد الزمني للبحث الخطي هو O (N) بينما البحث الثنائي له O (log₂N).
3. أفضل وقت للحالة في البحث الخطي هو للعنصر الأول ، على سبيل المثال ، O (1). في المقابل ، في البحث الثنائي ، يكون للعنصر الأوسط ، على سبيل المثال ، O (1).
4. في البحث الخطي ، فإن أسوأ حالة للبحث عن عنصر هي N عدد المقارنة. في المقابل ، هو سجل₂N عدد المقارنة للبحث الثنائي.
5. يمكن تنفيذ البحث الخطي في صفيف وكذلك في قائمة مرتبطة بينما لا يمكن تنفيذ البحث الثنائي مباشرة في القائمة المرتبطة.
6. كما نعلم ، فإن البحث الثنائي يتطلب مجموعة مصنفة وهذا هو السبب في أنه يتطلب معالجة لإدراجها في مكانها الصحيح للحفاظ على قائمة مرتبة. على العكس من ذلك ، لا يتطلب البحث الخطي عناصر مصنفة ، لذلك يتم إدراج العناصر بسهولة في نهاية القائمة.
7. البحث الخطي سهل الاستخدام ، وليس هناك حاجة لأي عناصر مرتبة. من ناحية أخرى ، تعتبر خوارزمية البحث الثنائي صعبة ، ويتم ترتيب العناصر بالترتيب بالضرورة.

استنتاج

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

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