الخوارزميات

خوارزمية البحث الخطي Linear Search Algorithm

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

طريقة عمل خوارزمية البحث الخطي

  1. لإجراء البحث الخطي لا بد من توفر عناصر أساسية و هي مصفوفة البحث و العنصر المُراد البحث عنه.
  2. بعكس كثير من خوارزميات البحث، لا يتطلب أن تكون مصفوفة البحث مرتبة ترتيباً تصاعدياً أو تنازلياً، هذا لا يعني أن المصفوفة إذا كانت مرتبة فإنها تُخل بأساسيات البحث الخطي، على العكس تماماً، فكل أنواع المصفوفات مرتبة أو غير مرتبة مُرحبٌ بها في خوارزمية البحث الخطي.
  3. مصفوفة البحث لها فهرس (Index)، يبدأ من الواحد أو الصفر، لا تختلف كثيراً فالنتيجة واحدة.
  4. يبدأ البحث بالتحقق من العنصر الأول هل هو مساوٍ للعُنصر المراد البحث عنه، إذا وُجد العنصر المراد البحث عنه يُحتفظ برقم الفهرس الخاص بالعنصر و تُنهى عملية البحث.
  5. إذا لم يُوجد العنصر المراد البحث عنه تنتقل عملية البحث من العنصر الأول في المصفوفة إلى العنصر الثاني ثم الثالث و هكذا إلى أن يكتمل البحث عن العُنصر المراد البحث عنه في كامل المصفوفة.
  6. يُرمز لحالة عدم إيجاد العُنصر المراد البحث عنه بقيمة مختلفة عن قيم فهرس المصفوفة، مثلاً إذا كانت المصفوفة بطول 10 عناصر، و تبدأ من 1 إلى 10، فيُرمز إلى حالة عدم إيجاد العنصر المراد البحث عنه بالرقم ( 0 )، لاحظ أنه كما ذُكر سابقاً في النقطة رقم 3، في بعض المصفوفات قد يبدأ الفهرس من الرقم صفر، في هذه الحالة قد يُلجأ إلى الإشارة بالقيمة NULL في حالة عدم إيجاد العنصر المراد البحث عنه.

مبادئ يجب أن نتفق عليها

  • نرمز إلى طول المصفوفة بالرمز n.
  • نرمز إلى العنصر المراد البحث عنه بالرمز x.
  • نرمز إلى مؤشر الفهرس بالرمز j.
  • نرمز إلى قيمة أي عنصر بالمصفوفة بالرمز [A[j.

مثال لطريقة البحث في خوارزمية البحث الخطي

لنفترض أن لدينا المصفوفة أدناه حيث n = 6 ، x=4

خوارزمية البحث الخطي

  •  تبدأ عملية البحث بمقارنة العنصر بالخانة رقم 1 حيث j=1، هل A[j]=x؟ لا. إذن ننتقل إلى الخطوة الثانية.
  • مقارنة العنصر بالخانة رقم 2 حيث j=2، هل A[j]=x؟ لا. إذن ننتقل إلى الخطوة الثالثة.
  • مقارنة العنصر بالخانة رقم 3 حيث j=3، هل A[j]=x؟ لا. إذن ننتقل إلى الخطوة الرابعة.
  • مقارنة العنصر بالخانة رقم 4 حيث j=4، هل A[j]=x؟ لا. إذن ننتقل إلى الخطوة الخامسة.
  • مقارنة العنصر بالخانة رقم 5 حيث j=5، هل A[j]=x؟ نعم. إذن هنا نحتفظ بالرقم 5 و تُعتبر هذه نتيجة البحث.

خوارزمية البحث الخطي

لا تستغرب تكرار المقارنات بحيث أن كل مقارنة وضعت في سطر حيث نُميز عدد المقارنات، معرفتك لعدد المقارنات ضروري لحساب أداء الخوارزمية.

حساب أفضل و أسواء حالة لخوارزمية البحث الخطي

سأختار أن أحسب أسوأ حالة لخوارزمية البحث الخطي إبتداءً: و لكن قبل أن تقرأ التالي، أُفضل أن تُفكر قليلاً و تحاول إستنتاج أسوأ حالة لهذه الخوارزمية، حتى تستطيع معرفة أسوأ حالة أصيغ لك السؤال بهذة الطريقة، ما هي الحالة التي تؤدي إلى أكبر عدد من المقارنات؟
فكر قليلاً … ثُم فكر … فكرت؟
إذا كانت إحابتك هي الحالة التي يكون فيها العُنصر المُراد البحث عنه في الخانة الأخيرة من المصوفة فتكون قد أجبت الإجابة الأكثر شُهرةً في الخطأ و جانبت الصواب بدرجة، ففي هذه الحالة التي ذكرتها يكون عدد المقارنات هو طول المصفوفة ناقصاً واحد، n-1.
الصواب هو أن أسوأ حالة لخوارزمية البحث الخطي هي عندما لا يكون العُنصر متواجداً بالمصفوفة، و بالتالي يكون عدد المقارنات يساوي طول المصفوفة n.

أفضل حالة لخوارزمية البحث الخطي هي بما لا يدع مجالاً للشك عندما يوجد العُنصر في أول خانة في المصفوفة، فيكون عد المقارنات هو مقارنة واحدة فقط.

الكود التقريبي لخوارزمية البحث الخطي Linear Search Pseudo Code

Input: An array A[1...n] of n elements and an element x.
Output: j if x = A[j]; 1<= j <= n, and 0 otherwise.
 j=1
 while (j < n) and (x != A[j])
 j=j + 1
 end while
 if x = A[j] then return j else return 0

خوارزمية البحث الخطي بلغة الجافا

import java.util.Scanner;
 
class LinearSearch 
{
  public static void main(String args[])
  {
    int c, n, search, array[];
 
    Scanner in = new Scanner(System.in);
    System.out.println("Enter number of elements");
    n = in.nextInt(); 
    array = new int[n];
 
    System.out.println("Enter " + n + " integers");
 
    for (c = 0; c < n; c++)
      array[c] = in.nextInt();
 
    System.out.println("Enter value to find");
    search = in.nextInt();
 
    for (c = 0; c < n; c++)
    {
      if (array[c] == search)     /* Searching element is present */
      {
         System.out.println(search + " is present at location " + (c + 1) + ".");
          break;
      }
   }
   if (c == n)  /* Searching element is absent */
      System.out.println(search + " is not present in array.");
  }
}

شُكراً لتواجدك في مدونة علوم، عبّر عن إعجابك بالتدوينة من هنا  و تسعدني مشاركتك لهذه التدوينة. و لا تنسى وضع تساؤلاتك و أفكارك و تعليقاتك أدناه.

الوسوم

مصطفى الطيب

صديقٌ لنُظمِ المعلُومات و عُلومِ الحَاسِب و مُختصٌ بهما، مُحبٌ للعِلمِ و نَشرِه. أُشاركُ معارفي و تَجاربي و خِبراتي في تَدويناتٍ و دوراتٍ من خلال مُدونةِ عُلوم.

مقالات ذات صلة

رأيان على “خوارزمية البحث الخطي Linear Search Algorithm”

  1. جُزيت الجنة أخي عزام، يُسعدني جداً جداً أن يكون ما أكتُبهُ مُفيداً للجميع، و يُسعدني سعدك أكثر و وجودك بين صفحات المدونة.

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *