خوارزميات البحث: البحث التسلسلي والبحث الثنائي (Recherche séquentielle et dichotomique) في Pascal — الثانية ثانوي (شعبة تقني رياضي) — الإعلام الآلي

🎯 أهداف التعلم

• أن يميز المتعلم بين البحث التسلسلي والبحث الثنائي.
• أن يطبق خوارزمية البحث التسلسلي على مصفوفة أحادية البعد بلغة Pascal.
• أن يطبق خوارزمية البحث الثنائي على مصفوفة مرتبة بلغة Pascal.
• أن يحلل كفاءة كل خوارزمية من حيث عدد المقارنات.
• أن يحل تمارين بكالوريا باستخدام خوارزميات البحث.

🔍 تمهيد

عند التعامل مع كميات كبيرة من البيانات، تصبح عملية البحث عن عنصر معين داخل مصفوفة (Tableau) من أهم المهارات البرمجية التي يجب أن يتقنها المبرمج. تخيل أن لديك دفتر عناوين يحوي 1000 اسم وتريد البحث عن اسم معين — كيف ستفعل ذلك؟ هل ستتصفح الأسماء واحداً تلو الآخر من البداية؟ أم أن هناك طريقة أسرع؟ في هذا الدرس، سنتعلم خوارزميتين أساسيتين للبحث في المصفوفات: البحث التسلسلي (Recherche séquentielle) و البحث الثنائي (Recherche dichotomique)، وسنطبقهما بلغة Pascal مع أمثلة وتمارين بكالوريا محلولة.

تجدر الإشارة إلى أن درسنا هذا يندرج ضمن وحدة الخوارزميات والبرمجة، وهو امتداد طبيعي لدرس المصفوفات (Tableaux) في لغة Pascal ودرس الدوال والإجراءات في لغة Pascal، حيث سنستخدم المصفوفات والدوال معاً في بناء خوارزميات البحث.

1️⃣ البحث التسلسلي (Recherche séquentielle / Linear Search)

1.1 المفهوم

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

1.2 المخطط الانسيابي

يمكن تمثيل خوارزمية البحث التسلسلي بمخطط انسيابي كالتالي:

• بداية ← إدخال N, T, X
• i ← 1
• حلقة تكرار: هل i ≤ N و T[i] ≠ X؟ نعم → i ← i + 1 ← كرر
• لا (خرجنا من الحلقة): هل i ≤ N؟
• نعم ← “العنصر موجود في الموقع i”
• لا ← “العنصر غير موجود”
• نهاية

1.3 البرمجة بلغة Pascal

لنكتب برنامجاً كاملاً يطبق البحث التسلسلي على مصفوفة من الأعداد الصحيحة:

Program RechercheSequencielle;
Uses WinCrt;
Var
  T : Array[1..100] of Integer;
  N, i, X : Integer;
  Trouve : Boolean;
Begin
  Write('أدخل عدد عناصر المصفوفة: ');
  ReadLn(N);
  
  { إدخال عناصر المصفوفة }
  For i := 1 to N Do
  Begin
    Write('T[', i, '] = ');
    ReadLn(T[i]);
  End;
  
  Write('أدخل القيمة المبحوث عنها X: ');
  ReadLn(X);
  
  { البحث التسلسلي }
  i := 1;
  Trouve := False;
  While (i <= N) and (Trouve = False) Do
  Begin
    If T[i] = X Then
      Trouve := True
    Else
      i := i + 1;
  End;
  
  { عرض النتيجة }
  If Trouve = True Then
    WriteLn('✅ العنصر ', X, ' موجود في الموقع ', i)
  Else
    WriteLn('❌ العنصر ', X, ' غير موجود في المصفوفة');
End.

1.4 تحليل الكفاءة

نلاحظ أن كفاءة البحث التسلسلي هي O(N) (خطية)، أي أن زمن البحث يتناسب طردياً مع حجم المصفوفة.

2️⃣ البحث الثنائي (Recherche dichotomique / Binary Search)

2.1 المفهوم

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

2.2 فكرة الخوارزمية

للبحث عن قيمة X في مصفوفة T مرتبة ترتيباً متزايداً ذات الحجم N:

1. نضع Gauche ← 1 (الحد الأيسر) و Droit ← N (الحد الأيمن)
2. طالما Gauche ≤ Droit:
   • نحسب Milieu ← (Gauche + Droit) Div 2
   • إذا كان T[Milieu] = X → العنصر موجود، توقف
   • إذا كان T[Milieu] < X → Gauche ← Milieu + 1 (ابحث في النصف الأيمن)
   • إذا كان T[Milieu] > X → Droit ← Milieu - 1 (ابحث في النصف الأيسر)
3. إذا انتهت الحلقة دون العثور → العنصر غير موجود.

2.3 البرمجة بلغة Pascal

Program RechercheDichotomique;
Uses WinCrt;
Var
  T : Array[1..100] of Integer;
  N, i, X, Gauche, Droit, Milieu : Integer;
  Trouve : Boolean;
Begin
  Write('أدخل عدد عناصر المصفوفة: ');
  ReadLn(N);
  
  { إدخال عناصر المصفوفة (مرتبة تصاعدياً) }
  For i := 1 to N Do
  Begin
    Write('T[', i, '] = ');
    ReadLn(T[i]);
  End;
  
  Write('أدخل القيمة المبحوث عنها X: ');
  ReadLn(X);
  
  { البحث الثنائي }
  Gauche := 1;
  Droit := N;
  Trouve := False;
  
  While (Gauche <= Droit) and (Trouve = False) Do
  Begin
    Milieu := (Gauche + Droit) Div 2;
    If T[Milieu] = X Then
      Trouve := True
    Else If T[Milieu] < X Then
      Gauche := Milieu + 1   { ابحث في النصف الأيمن }
    Else
      Droit := Milieu - 1;   { ابحث في النصف الأيسر }
  End;
  
  { عرض النتيجة }
  If Trouve = True Then
    WriteLn('✅ العنصر ', X, ' موجود في الموقع ', Milieu)
  Else
    WriteLn('❌ العنصر ', X, ' غير موجود في المصفوفة');
End.

2.4 مثال توضيحي خطوة بخطوة

2.5 تحليل الكفاءة

كفاءة البحث الثنائي هي O(log N) (لوغاريتمية)، وهي أفضل بكثير من O(N). لمصفوفة تحتوي على 1000 عنصر، يحتاج البحث التسلسلي إلى 1000 مقارنة في أسوأ الحالات، بينما يحتاج البحث الثنائي إلى 10 مقارنات فقط!

3️⃣ مقارنة بين الخوارزميتين

✏️ تمارين بكالوريا محلولة

Program ChercherPremier;
Uses WinCrt;
Var
  T : Array[1..100] of Integer;
  N, i, j : Integer;
  EstPremier : Boolean;
  Trouve : Boolean;
Begin
  Write('أدخل عدد عناصر المصفوفة: ');
  ReadLn(N);
  
  For i := 1 to N Do
  Begin
    Write('T[', i, '] = ');
    ReadLn(T[i]);
  End;
  
  { البحث عن أول عدد أولي }
  i := 1;
  Trouve := False;
  
  While (i <= N) and (Trouve = False) Do
  Begin
    If T[i] > 1 Then
    Begin
      EstPremier := True;
      j := 2;
      While (j <= Sqrt(T[i])) and (EstPremier = True) Do
      Begin
        If T[i] Mod j = 0 Then
          EstPremier := False
        Else
          j := j + 1;
      End;
      If EstPremier Then
        Trouve := True
      Else
        i := i + 1;
    End
    Else
      i := i + 1;
  End;
  
  If Trouve = True Then
    WriteLn('✅ أول عدد أولي هو ', T[i], ' في الموقع ', i)
  Else
    WriteLn('❌ لا يوجد عدد أولي في المصفوفة');
End.

Program RechercheEtInsertion;
Uses WinCrt;
Var
  T : Array[1..200] of Integer;
  N, i, X, G, D, M, Pos : Integer;
  Trouve : Boolean;
Begin
  Write('أدخل عدد عناصر المصفوفة: ');
  ReadLn(N);
  
  For i := 1 to N Do
  Begin
    Write('T[', i, '] = ');
    ReadLn(T[i]);
  End;
  
  Write('أدخل القيمة المبحوث عنها X: ');
  ReadLn(X);
  
  { البحث الثنائي }
  G := 1;
  D := N;
  Trouve := False;
  
  While (G <= D) and (Trouve = False) Do
  Begin
    M := (G + D) Div 2;
    If T[M] = X Then
      Trouve := True
    Else If T[M] < X Then
      G := M + 1
    Else
      D := M - 1;
  End;
  
  If Trouve = True Then
    WriteLn('✅ العنصر موجود في الموقع ', M)
  Else
  Begin
    { إدراج X في المكان المناسب }
    Pos := G;  { الموقع المناسب للإدراج }
    
    { إزاحة العناصر إلى اليمين }
    For i := N DownTo Pos Do
      T[i + 1] := T[i];
    
    T[Pos] := X;
    N := N + 1;
    
    WriteLn('➕ تم إدراج ', X, ' في الموقع ', Pos);
    WriteLn('المصفوفة بعد الإدراج:');
    For i := 1 to N Do
      Write(T[i], ' ');
  End;
End.

📌 ملخص الدرس

📍 دروس مشابهة:

• المصفوفات (Tableaux) في لغة Pascal — أحادية وثنائية البعد — الثانية ثانوي (شعبة تقني رياضي) — الإعلام الآلي
• الدوال والإجراءات في لغة Pascal (Functions et Procedures) — الثانية ثانوي (شعبة تقني رياضي) — الإعلام الآلي