واحدة من الخوارزميات الأساسية في علوم الكمبيوتر هي خوارزمية البحث الثنائي. يمكنك تنفيذ البحث الثنائي باستخدام طريقتين: الطريقة التكرارية والطريقة العودية. في حين أن كلتا الطريقتين لهما نفس التعقيد الزمني ، فإن الطريقة التكرارية أكثر كفاءة من حيث تعقيد الفضاء.
الطريقة التكرارية لها تعقيد مساحة يا (1) مقارنة ب O (تسجيل الدخول) التي تنتجها الطريقة العودية. إذن ، كيف يمكنك تنفيذ خوارزمية البحث الثنائي باستخدام الطريقة التكرارية في C و C ++ و Python؟
ما هو البحث الثنائي؟
البحث الثنائي المعروف أيضًا باسم البحث نصف الفاصل أو البحث اللوغاريتمي أو الفرم الثنائي هو خوارزمية تبحث وتعيد موضع عنصر في مصفوفة مرتبة. تتم مقارنة عنصر البحث بالعنصر الأوسط. بأخذ متوسط الحدين الأدنى والأعلى ، يمكنك إيجاد العناصر الوسطى.
إذا كان عنصر البحث أكبر من العنصر الأوسط ، فهذا يعني أن جميع العناصر الموجودة على الجانب الأيسر أصغر من عنصر البحث. لذلك ، ينتقل عنصر التحكم إلى الجانب الأيمن من المصفوفة (إذا كانت المصفوفة بترتيب تصاعدي) عن طريق زيادة الحد الأدنى إلى الموضع التالي للعنصر الأوسط.
وبالمثل ، إذا كان عنصر البحث أصغر من العنصر الأوسط ، فهذا يعني أن جميع العناصر الموجودة على الجانب الأيمن أكبر من عنصر البحث. لذلك ، ينتقل عنصر التحكم إلى الجزء الأيسر من المصفوفة عن طريق تغيير الحد الأعلى إلى الموضع السابق للعنصر الأوسط.
هذا يقلل بشكل كبير من عدد المقارنات بالمقارنة مع تنفيذ البحث الخطي حيث أن عدد المقارنات يساوي عدد العناصر في سيناريو أسوأ حالة. أثبتت هذه الطريقة أنها مفيدة جدًا للعثور على الأرقام في دليل الهاتف أو الكلمات في القاموس.
إليك تمثيل تخطيطي لـ خوارزمية البحث الثنائي:
البحث الثنائي باستخدام C
اتبع هذه الخطوات لتنفيذ Binary Search باستخدام C:
الكود المصدري الكامل لبرنامج Binary Search باستخدام C و C ++ و Java و Python موجود في هذا مستودع جيثب.
يحدد البرنامج وظيفة ، بحث ثنائي()، التي تُرجع إما فهرس القيمة التي تم العثور عليها أو -1 إذا لم يكن موجودًا:
#يشمل <stdio.h>
intبحث ثنائي(int arr [] ، int arr_size ، int search_number){
/*... */
}
تعمل الوظيفة عن طريق تضييق مساحة البحث بشكل متكرر. نظرًا لأن البحث الثنائي يعمل على المصفوفات المصنفة ، يمكنك حساب الوسط الذي لا معنى له بخلاف ذلك. يمكنك إما أن تطلب من المستخدم مصفوفة مرتبة أو استخدام خوارزميات الفرز مثل Bubble أو Selection Sort.
ال قليل و عالي المتغيرات تخزن الفهارس التي تمثل حدود مساحة البحث الحالية. منتصف يخزن الفهرس في المنتصف:
int منخفض = 0، مرتفع = حجم arr_size - 1، منتصفالرئيسية بينما() حلقة سوف تضيق مساحة البحث. إذا أصبحت قيمة المؤشر المنخفض أكبر من المؤشر المرتفع ، فهذا يعني أن مساحة البحث قد استنفدت ، وبالتالي لا يمكن أن تكون القيمة موجودة.
بينما (منخفض <= مرتفع) {
/* متواصل... [1] */
}
يعود-1;
بعد تحديث نقطة المنتصف في بداية الحلقة ، هناك ثلاث نتائج محتملة:
- إذا كانت القيمة عند نقطة المنتصف هي القيمة التي نبحث عنها ، فقم بإرجاع هذا الفهرس.
- إذا كانت قيمة النقطة المتوسطة أكبر من القيمة التي نبحث عنها ، فقم بتقليل القيمة العالية.
- إذا كانت قيمة النقطة المتوسطة أقل ، قم بزيادة القيمة المنخفضة.
/ * [1]... تابع * /
منتصف = (منخفض + (مرتفع - منخفض)) / 2 ؛
إذا (arr [mid] == search_number)
يعود منتصف ؛
آخرلو (arr [mid]> search_number)
مرتفع = منتصف - 1 ؛
آخر
منخفض = منتصف + 1 ؛
اختبر الوظيفة بإدخال المستخدم. يستخدم scanf () للحصول على مدخلات من سطر الأوامر ، بما في ذلك حجم المصفوفة ومحتوياتها ورقم للبحث عنه:
intرئيسي(){
int الوصول [100] ، أنا ، arr_size ، search_number ؛
printf ("أدخل عدد العناصر: ");
scanf ("٪د", &arr_size) ؛
printf ("الرجاء إدخال الأرقام: ");لـ (أنا = 0 ؛ أنا < حجم أنا ++) {
scanf ("٪د", &arr [i]) ؛
}printf ("أدخل الرقم المراد البحث عنه: ");
scanf ("٪د", &search_number) ؛i = binarySearch (arr، arr_size، search_number) ؛
إذا (أنا == - 1)
printf ("الرقم غير موجود");
آخر
printf ("الرقم موجود في الموضع٪ d"، أنا + 1) ؛
يعود0;
}
إذا وجدت الرقم ، اعرض موضعه أو فهرسه ، وإلا ستظهر رسالة تفيد بعدم وجود الرقم.
بحث ثنائي باستخدام C ++
يمكنك تحويل برنامج C إلى برنامج C ++ عن طريق استيراد ملف دفق إخراج الإدخال و استخدام مساحة الاسم المنقولة جنسيا لتجنب تكراره عدة مرات خلال البرنامج.
#يشمل <iostream>
استخدام مساحة الاسمالأمراض المنقولة جنسيا;يستخدم كوت مع مشغل الاستخراج << بدلاً من printf () و سين مع مشغل الإدخال >> بدلاً من scanf () وبرنامج C ++ جاهز.
printf ("أدخل عدد العناصر: ");
كوت <<"أدخل عدد العناصر: ";
scanf ("٪د", &arr_size) ؛
سين >> حجمبحث ثنائي باستخدام بايثون
نظرًا لأن Python لا تحتوي على دعم داخلي للمصفوفات ، استخدم القوائم. تحديد وظيفة ، بحث ثنائي()، التي تقبل ثلاث معاملات ، القائمة ، وحجمها ، ورقم للبحث عنها:
defبحث ثنائي(arr، arr_size، search_number):
منخفض = 0
ارتفاع = حجم_العرض - 1
بينما منخفض <= مرتفع:
متوسط = منخفض + (عالي-منخفض)//2
إذا arr [mid] == search_number:
يعود منتصف
أليف arr [منتصف]> search_number:
عالية = منتصف - 1
آخر:
منخفض = منتصف + 1
يعود-1تهيئة متغيرين ، قليل و عالي، ليكون بمثابة الحد الأدنى والأعلى للقائمة. على غرار تنفيذ C ، استخدم أ بينما حلقة تضيق مساحة البحث. التهيئة منتصف لتخزين القيمة الوسطى للقائمة. توفر Python عامل تقسيم الأرضية (//) الذي يوفر أكبر عدد صحيح ممكن.
قم بإجراء المقارنات وتضييق مساحة البحث حتى تساوي القيمة المتوسطة رقم البحث. في حالة عدم وجود رقم البحث ، سيعود عنصر التحكم -1.
arr_size = int (المدخلات ("أدخل عدد العناصر: "))
arr = []
مطبعة("الرجاء إدخال الأرقام: "، النهاية ="")
بالنسبة لـ i في النطاق (0، arr_size):
arr.append (int(مدخل()))
search_number = int (المدخلات ("أدخل الرقم المراد البحث عنه: "))
النتيجة = binarySearch (arr، arr_size، search_number)
إذا كانت النتيجة == -1:
مطبعة("الرقم غير موجود")
آخر:
print ("Number يكون موجود في الموضع "، (نتيجة + 1))اختبر الوظيفة بإدخال المستخدم. يستخدم مدخل() للحصول على حجم القائمة ومحتوياتها ورقم للبحث عنه. يستخدم int () لنسخ إدخال السلسلة المقبولة بواسطة Python كإعداد افتراضي في عدد صحيح. لإضافة أرقام إلى القائمة ، استخدم ألحق() وظيفة.
يتصل بحث ثنائي() وتمرير الحجج. إذا وجدت الرقم ، اعرض موضعه أو فهرسه ، وإلا ستظهر رسالة تفيد بعدم وجود الرقم.
ناتج خوارزمية البحث الثنائي
ما يلي هو ناتج خوارزمية البحث الثنائي عندما يكون العنصر موجودًا في المصفوفة:
ما يلي هو ناتج خوارزمية البحث الثنائي عندما لا يكون العنصر موجودًا في المصفوفة:
تعلم هياكل البيانات الأساسية والخوارزميات
يعد البحث أحد الخوارزميات الأولى التي تتعلمها وغالبًا ما يُطلب منك ذلك في مسابقات الترميز والمواضع والمقابلات. بعض الخوارزميات الأخرى التي يجب أن تتعلمها هي خوارزميات الفرز والتجزئة والبرمجة الديناميكية ومطابقة السلسلة واختبار البدائية.
بالإضافة إلى ذلك ، من الضروري فهم الوقت والمساحة المعقدة للخوارزميات. إنها واحدة من أهم المفاهيم في علوم الكمبيوتر في تحديد كفاءة أي خوارزمية. من خلال المعرفة بهياكل البيانات والخوارزميات ، فإنك ملزم ببناء أفضل البرامج.
