بحث ثنائي

البحث الثنائي هو & mdash؛ تقدير درجة تعقيدها هو O (log2 (n)) ، بينما البحث المتسلسل التقليدي يحتوي على O (n) . هذا يعني أنه ، على سبيل المثال ، بالنسبة لمصفوفة من 1024 عنصرًا ، فإن البحث الخطي ، في أسوأ الحالات ، عندما لا يكون العنصر المطلوب في المصفوفة ، سيعالج جميع العناصر البالغ عددها 1024. البحث الثنائي كافٍ لمعالجة عناصر \ (log_2 (1024) = 10 \) . يتم تحقيق هذه النتيجة بسبب حقيقة أنه بعد الخطوة الأولى من الحلقة ، تضيق منطقة البحث إلى 512 عنصرًا ، بعد الثانية & ndash ؛ حتى 256 إلخ. تتمثل عيوب هذه الخوارزمية في الحاجة إلى ترتيب البيانات ، فضلاً عن القدرة على الوصول إلى أي عنصر بيانات في وقت ثابت (بغض النظر عن كمية البيانات). وبالتالي ، لا يمكن للخوارزمية أن تعمل على المصفوفات غير المرتبة وأي هياكل بيانات تعتمد على القوائم المرتبطة.

التنفيذ

 وداعًا  (يمين & ndash؛ يسار  & gt؛   1 )  // طالما أن الحد الأيمن على يمين اليسار 
 nc 
  الأوسط  =  (يسار  +  يمين)  / < / span>  2 ؛  // وسط منطقة البحث 
   if  (A [middle]  & gt؛ =  ب)  ثم 
    يمين  =  mid؛  // تحريك الحد الأيمن 
   بخلاف ذلك 
    يسار  =  mid؛  // وبخلاف ذلك انقل الحد الأيسر 
 سم مكعب 
 if  (A [right]  ==  X)  ثم 
  الإخراج الصحيح
 بخلاف ذلك 
  الإخراج  - 1  ؛