Module: البحث الخطي والثنائي عن العناصر في المصفوفة


Problem

6/7

بحث ثنائي

Theory Click to read/hide

بحث ثنائي
البحث الثنائي (أو الثنائي) هو خوارزمية بحث فعالة وأسرع من البحث الخطي. على سبيل المثال ، بالنسبة لمصفوفة من 1024 عنصرًا ، فإن البحث الخطي في أسوأ الحالات (عندما لا يكون العنصر المطلوب في المصفوفة) سيعالج جميع العناصر البالغ عددها 1024 ، ولكن يكفي معالجة 10 عناصر ببحث ثنائي. يتم تحقيق هذه النتيجة بسبب حقيقة أنه بعد الخطوة الأولى من الحلقة ، تضيق منطقة البحث إلى 512 عنصرًا ، بعد الثانية & ndash ؛ ما يصل إلى 256 إلخ.
& nbsp؛
تتمثل عيوب هذه الخوارزمية في متطلبات ترتيب البيانات ، فضلاً عن القدرة على الوصول إلى أي عنصر بيانات في وقت ثابت (بغض النظر عن كمية البيانات). لذلك ، لا يمكن أن تعمل الخوارزمية على المصفوفات غير المرتبة.
نبسب ؛
الخوارزمية
  1. حدد العنصر الأوسط A [c] والمقارنة بـ X .
  2. إذا كان X = A [c] ثم تم العثور على (توقف).
  3. إذا كان X & lt؛ أ [ج] ، ابحث أكثر في الشوط الأول.
  4. إذا كان X & gt؛ & nbsp؛ A [c] ، فابحث في النصف الثاني.
    نبسب ؛
التنفيذ L = 0 ؛ R = N ؛ // الجزء الأولي بينما (L & lt ؛ R - 1) { ج = (L + R) / 2 ؛ // وجد الوسط إذا (X & lt؛ A [c]) // ضغط المقطع ص = ج ؛ آخر L = ج ؛ } إذا (A [L] == X) كوت & lt؛ & lt؛ & quot؛ ا & quot؛ & lt؛ & lt؛ L & lt؛ & lt؛ & quot؛] = & quot؛ & lt؛ & lt؛ العاشر ؛ آخر كوت & lt؛ & lt؛ & quot؛ غير موجود & quot ؛؛

حيث:
A - مصفوفة المصدر ،
N - حجم المصفوفة ،
X - الرقم الذي تم البحث عنه ،

تطبيقات أخرى ممكنة.
على سبيل المثال ، استخدام مخرج مبكر من الحلقة L = 0 ؛ R = N - 1 ؛ بينما (R & GT ؛ = L) { ج = (L + R) / 2 ؛ إذا (X == A [c]) { ن س = ج ؛ استراحة؛ } إذا (X & lt؛ A [ج]) R = منتصف - 1 ؛ إذا (X & gt؛ A [c]) L = mid + 1 ؛ } إذا (nX & lt؛ 0) كوت & lt؛ & lt؛ & quot؛ غير موجود & quot ؛؛ آخر كوت & lt؛ & lt؛ & quot؛ ا & quot؛ & lt؛ & lt؛ nX & lt؛ & lt؛ & quot؛] = & quot؛ & lt؛ & lt؛ X ؛

Problem

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

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include<iostream> 
using namespace std; 
main() 
{	
  const int Nmax=1000; 	
  int A[Nmax], i, L, R, X, N, c;	 
  cin >> N; 
  for (i=0; i<N; i++) 
    cin >> A[i]; 
  cin >> X; 
  L = 0; R = N;       
  while ( L < R-1 )     
       cout << "A["<< L << "]=" << X; 
  else cout << "Not found"; 
}

     

Program check result

To check the solution of the problem, you need to register or log in!