البحث الخطي مقابل البحث الثنائي: الفرق بين البحث الخطي والبحث الثنائي
نشرت: 2021-02-09جدول المحتويات
مقدمة
يوفر تخصيص الذاكرة المتجاورة في لغات البرمجة تنفيذًا مرنًا لتخزين نقاط بيانات متعددة. يمكن استخدام هذا في ذروته إذا أردنا فصل البيانات ودمج جميع البيانات المتشابهة في بنية بيانات متجاورة مثل المصفوفة أو القائمة أو ما إلى ذلك.
يحتوي تخصيص الذاكرة المتجاورة على العديد من التطبيقات في تطبيقات العالم الحقيقي مثل نظام التشغيل في أجهزة الكمبيوتر وأنظمة إدارة قواعد البيانات وما إلى ذلك. تعتبر بنية البيانات هذه هيكلًا مرنًا لأن إضافة نقطة بيانات جديدة إلى مصفوفة تتطلب فقط وحدة زمنية واحدة مثل ؛ يا (1).
لكن المشكلة تنشأ عندما نريد النظر في إدخال معين أو البحث عن إدخال معين لأن جميع تطبيقات العالم الحقيقي تعتمد على أوامر الوصول إلى البيانات. ويجب أن تكون هذه المهمة سريعة بما يكفي لتلبية سرعة المعالج والذاكرة.
هناك خوارزميات بحث متنوعة مقسمة بناءً على عدد المقارنات التي نجريها للبحث في العنصر.
إذا قارنا كل نقطة بيانات في المصفوفة للبحث عن عنصر ، فسيتم اعتباره بحثًا متسلسلًا. ولكن إذا كنا نقارن فقط عددًا قليلاً من العناصر عن طريق تخطي بعض المقارنات ، فسيتم اعتبارها بحثًا بفاصل زمني. لكننا نحتاج إلى مصفوفة مرتبة بترتيب (ترتيب تصاعدي أو تنازلي) لإجراء بحث فاصل عليها.
التعقيد الزمني للبحث المتسلسل هو خطي O (n) ، والتعقيد الزمني للبحث الثنائي (مثال على البحث الفاصل) هو O (log n). أيضًا ، هناك خوارزميات بحث أخرى مثل البحث الأسي والبحث السريع وما إلى ذلك.
ولكن يتم استخدام البحث الخطي والبحث الثنائي في الغالب ، حيث يكون البحث الخطي عن بيانات عشوائية أو غير مرتبة والبحث الثنائي عن البيانات المرتبة والمرتبة. التجزئة هي خوارزمية بحث خاصة حيث يكون التعقيد الزمني للوصول إلى نقطة بيانات هو O (1).
دعنا أولاً نتصفح خوارزميات البحث الخطي والبحث الثنائي ثم نقارن الاختلافات بين البحث الخطي والبحث الثنائي.
البحث الخطي
كما تمت مناقشته بالفعل ، تقارن خوارزمية البحث الخطي كل عنصر في المصفوفة ، وإليك الكود للقيام بذلك.
| فئة عامة UpGrad { public static int linear_search ( int [] arr، int n، int k) { لـ ( int i = 0 ؛ i <n ؛ i ++) إذا (arr [i] == k) العودة أنا + 1 ؛ عودة - 1 ؛ } العامة الثابتة الفراغ الرئيسي (سلسلة [] args) { int [] arr = new int [] { 1 ، 2 ، 5 ، 6 ، 3 ، 8 ، 9 ، 9 ، 0 ، 13 ، 45 ، 65 } ؛ كثافة العمليات ك = 13 ؛ int n = طول الطول ؛ int r = linear_search (arr، n، k) ؛ إذا (ص == - 1 ) System.out.println ( "العنصر غير موجود" ) ؛ آخر System.out.println ( "عنصر موجود في موضع" + r + " ) ؛ } } |
دعنا نتصفح الكود.
لقد أعلنا عن دالة linear_search ، والتي تتوقع مصفوفة ، مفتاح عدد صحيح كمعلمات. نحتاج الآن إلى إجراء حلقة فوق جميع العناصر ومقارنة ما إذا كان يتطابق مع مفتاح البحث الخاص بنا ، لذلك قمنا بكتابة حلقة for التي تدور فوق المصفوفة ، وداخلها ، توجد حلقة if التي تتحقق مما إذا كان الرقم الموجود في هذا الموضع متطابقًا بمفتاح البحث أم لا. إذا وجدنا تطابقًا فسنقوم بإرجاع المركز. إذا لم يكن هناك عنصر من هذا القبيل في المصفوفة ، فسنعود -1 في نهاية الدالة.
لاحظ أنه إذا كان لدينا عدة مظاهر لنفس الرقم ، فسنقوم بإرجاع موضع تكراره لأول مرة.
بالانتقال إلى الطريقة الرئيسية ، قمنا بتعريف وتهيئة مصفوفة عدد صحيح. ثم نقوم بتهيئة المفتاح الذي يجب البحث عنه. نحن هنا نقوم بترميز المصفوفة والمفتاح بشكل ثابت ، ولكن يمكنك تغييره إلى إدخال المستخدم. الآن وقد حصلنا على قائمة العناصر والمفتاح المراد البحث عنه ، يتم استدعاء طريقة البحث الخطي ويتم تدوين الفهرس الذي تم إرجاعه. لاحقًا ، نتحقق من القيمة التي تم إرجاعها ونطبع الفهرس إذا كان المفتاح موجودًا ، وإلا لم يتم العثور على مفتاح الطباعة.
بحث ثنائي
البحث الثنائي هو الأمثل أكثر من البحث الخطي ، ولكن يجب فرز المصفوفة لتطبيق البحث الثنائي. وإليك الكود للقيام بذلك.
| فئة عامة UpGrad { public static int binary_search ( int [] arr، int k) { int l = 0 ، h = arr.length- 1 ، mid = 0 ؛ بينما (ل <= ح) { منتصف = l + (hl) / 2 ؛ إذا (arr [mid] == k) عودة منتصف + 1 ؛ وإلا إذا (arr [mid]> k) ح = منتصف -1 ؛ آخر ل = منتصف + 1 ؛ } عودة - 1 ؛ } العامة الثابتة الفراغ الرئيسي (سلسلة [] args) { int [] arr = new int [] { 1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 7 ، 8 ، 9 } ؛ كثافة العمليات ك = 8 ؛ int r = binary_search (arr، k) ؛ إذا (ص == - 1 ) System.out.println ( "العنصر غير موجود" ) ؛ آخر System.out.println ( "عنصر موجود في موضع" + r + " ) ؛ } } |
دعنا نتصفح الكود.
لقد أعلنا عن طريقة binary_search والتي تتوقع مصفوفة أعداد صحيحة مرتبة ومفتاح عدد صحيح كمعامِلات. نقوم بتهيئة المتغيرات منخفضة وعالية ومتوسطة. هنا منخفضة ، أعلى هي المؤشرات حيث سيكون الانخفاض عند مؤشر 0 والأعلى سيكون عند مؤشر n في البداية. فكيف يعمل البحث الثنائي؟
في البداية ، سنحسب منتصف المنخفض والعالي. يمكننا حساب الوسط كـ (منخفض + مرتفع) / 2 ، ولكن في بعض الأحيان قد يكون الارتفاع عددًا كبيرًا ، وقد يؤدي إضافة قيمة منخفضة إلى القمة إلى تجاوز عدد صحيح. لذا فإن حساب متوسط منخفض + (عالي-منخفض) / 2 سيكون الطريقة المثلى.
سنقارن العنصر في المنتصف بمفتاح البحث ، وسنعيد الفهرس إذا وجدنا تطابقًا. وإلا سنتحقق مما إذا كان العنصر الأوسط أكبر من المفتاح أم أصغر من المفتاح. إذا كان الوسط أكبر ، فسنحتاج إلى التحقق من النصف الأول فقط من المصفوفة لأن جميع العناصر في النصف الثاني من المصفوفة أكبر من المفتاح ، لذلك سنقوم بتحديث الارتفاع إلى المنتصف 1.
وبالمثل ، إذا كان mid أقل من مفتاح ، فإننا نحتاج إلى البحث في النصف الثاني من المصفوفة ، ومن ثم نقوم بتحديث منخفض إلى متوسط + 1. تذكر أن البحث الثنائي يعتمد على خوارزمية التصغير والقهر لأننا نتجاهل أحد نصفي المصفوفة في كل تكرار.
بالعودة إلى الكود الخاص بنا ، قمنا ببناء الطريقة الرئيسية. تهيئة مصفوفة مرتبة ومفتاح بحث ، وإجراء استدعاء للبحث الثنائي ، وطباعة النتائج.
الآن بعد أن مررنا عبر خوارزميات كل من البحث الخطي والبحث الثنائي ، دعنا نقارن كلا الخوارزميات.
البحث الخطي مقابل البحث الثنائي
عمل
- يتكرر البحث الخطي عبر جميع العناصر ويقارنها بالمفتاح الذي يجب البحث عنه.
- يقلل البحث الثنائي بحكمة حجم المصفوفة التي يجب البحث عنها ويقارن المفتاح بالعنصر الأوسط في كل مرة.
هيكل البيانات
- البحث الخطي مرن مع جميع هياكل البيانات مثل المصفوفة والقائمة والقائمة المرتبطة وما إلى ذلك.
- لا يمكن إجراء بحث ثنائي على جميع هياكل البيانات لأننا نحتاج إلى اجتياز متعدد الاتجاهات. لذلك لا يمكن استخدام هياكل البيانات مثل القائمة المرتبطة المفردة.
المتطلبات الأساسية
- يمكن إجراء البحث الخطي على جميع أنواع البيانات ، ويمكن أن تكون البيانات عشوائية أو يتم فرزها ، حيث تظل الخوارزمية كما هي. لذلك لا داعي للقيام بأي عمل مسبق.
- البحث الثنائي يعمل فقط على مصفوفة مرتبة. لذا فإن فرز المصفوفة هو شرط أساسي لهذه الخوارزمية.
حالة الاستخدام
- يُفضل البحث الخطي بشكل عام لمجموعات البيانات المرتبة الأصغر والعشوائية.
- يُفضل البحث الثنائي لمجموعات البيانات الأكبر والمفروزة نسبيًا.
فعالية
- البحث الخطي أقل كفاءة في حالة مجموعات البيانات الأكبر.
- يكون البحث الثنائي أكثر كفاءة في حالة مجموعات البيانات الأكبر.
تعقيد الوقت
- في البحث الخطي ، أفضل حالة تعقيد هي O (1) حيث يوجد العنصر في الفهرس الأول. أسوأ حالة تعقيد هي O (n) حيث يوجد العنصر في الفهرس الأخير أو العنصر غير موجود في المصفوفة.
- في البحث الثنائي ، أفضل حالة تعقيد هي O (1) حيث يوجد العنصر في الفهرس الأوسط. التعقيد الأسوأ هو O ( log 2 n).
ركض جاف
لنفترض أن لدينا مصفوفة بحجم 10000.
- في البحث الخطي ، يكون تعقيد أفضل حالة هو O (1) وأسوأ حالة تعقيد هو O (10000).
- في البحث الثنائي ، يكون تعقيد أفضل حالة هو O (1) وتعقيد الحالة الأسوأ هو O ( السجل 2 10000) = O (13.287).
خاتمة
لقد فهمنا أهمية الوصول إلى البيانات في المصفوفات ، وفهمنا الخوارزميات للبحث الخطي والبحث الثنائي. مشى من خلال رموز البحث الخطي والبحث الثنائي. مقارنة الاختلافات بين البحث الخطي والبحث الثنائي ، قم بإجراء تشغيل جاف لمثال كبير الحجم.
الآن بعد أن أصبحت على دراية بالاختلافات بين البحث الخطي والبحث الثنائي ، حاول تشغيل كلا الرمزين لمجموعة بيانات كبيرة الحجم وقارن وقت التنفيذ ، وابدأ في استكشاف خوارزميات بحث مختلفة ، وحاول تنفيذها!
إذا كنت مهتمًا بالتعرف على علوم البيانات ، فراجع دبلوم PG في IIIT-B & upGrad في علوم البيانات والذي تم إنشاؤه للمهنيين العاملين ويقدم أكثر من 10 دراسات حالة ومشاريع ، وورش عمل عملية عملية ، وإرشاد مع خبراء الصناعة ، 1- على - 1 مع موجهين في الصناعة ، وأكثر من 400 ساعة من التعلم والمساعدة في العمل مع الشركات الكبرى.
تعلم دورات علوم البيانات عبر الإنترنت من أفضل الجامعات في العالم. اربح برامج PG التنفيذية أو برامج الشهادات المتقدمة أو برامج الماجستير لتتبع حياتك المهنية بشكل سريع.
قارن البحث الخطي والبحث الثنائي باستخدام تعقيداتهما.
يعتبر البحث الثنائي أكثر كفاءة وفعالية من البحث الخطي من نواح كثيرة ، خاصة عندما تكون العناصر مرتبة بترتيب. يتلخص السبب في تعقيدات عمليتي البحث.
البحث الخطي
1. تعقيد الوقت: O (N) - نظرًا لأننا في البحث الخطي ، ننتقل عبر المصفوفة للتحقق مما إذا كان أي عنصر يطابق المفتاح. في أسوأ السيناريوهات ، سيكون العنصر موجودًا في نهاية المصفوفة ، لذا يتعين علينا اجتياز النهاية ، وبالتالي سيكون التعقيد الزمني هو O (N) حيث N هو العدد الإجمالي لعناصر المصفوفة.
2. تعقيد الفضاء: O (1) - نحن لا نستخدم أي مساحة إضافية لذلك سيكون التعقيد المكاني O (1).
بحث ثنائي
1. تعقيد الوقت: O (log N) - في البحث الثنائي ، ينخفض البحث إلى النصف حيث يتعين علينا فقط البحث عن منتصف المصفوفة. ونقوم باستمرار بتقصير بحثنا إلى منتصف القسم الذي يوجد فيه العنصر.
2. التعقيد المكاني: O (1)
- نحن لا نستخدم أي مساحة إضافية لذا فإن التعقيد المكاني سيكون O (1).
هل هناك أي طريقة أخرى للبحث عن عنصر في المصفوفة؟
على الرغم من استخدام البحث الخطي والبحث الثنائي غالبًا للبحث ، إلا أن هناك بالفعل طريقة بحث أخرى - طريقة الاستيفاء. إنها نسخة محسنة من Binary Search حيث يتم توزيع جميع العناصر بشكل موحد.
الفكرة من وراء هذه الطريقة هي أنه في البحث الثنائي ، نبحث دائمًا عن منتصف المصفوفة. ولكن في هذه الطريقة ، يمكن أن ينتقل البحث إلى مواقع مختلفة اعتمادًا على مكان وجود المفتاح. على سبيل المثال ، إذا كان المفتاح موجودًا بالقرب من العنصر الأخير في المصفوفة ، فسيبدأ البحث من نهاية المصفوفة.
ما هي التعقيدات الزمنية المختلفة لبحث الاستيفاء؟
أسوأ حالة تعقيد زمني لبحث الاستيفاء هي O (N) لأنه في أسوأ الحالات ، سيكون المفتاح في نهاية المصفوفة لذلك يجب على المكرر المرور عبر المصفوفة.
سيكون متوسط تعقيد الحالة هو O (السجل (السجل N) نظرًا لأن العنصر يمكن أن يكون في أي مكان في المصفوفة. وقد يكون بالقرب من نقطة البداية أيضًا.
سيكون أفضل تعقيد في الحالة هو O (1) لأنه ، في أفضل الأحوال ، سيكون المفتاح هو العنصر الأول في المصفوفة.