خوارزمية البحث المستقيم Linear Search

-

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

في هذه الصورة المطلوب البحث عن الرقم 39 . لاحظ من الصورة ان البحث يتم بشكل متسلسل حتى الوصول الى هذا الرقم المطلوب. 

خوارزمية البحث المستقيم  

في هذه الخوارزمية المطلوب البحث عن القيمة x في المصفوفة A .

Linear Search ( Array A, Value x)
Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit

شرح الخوارزمية

• عرفنا متغير باسم i للمرور على جميع عناصر المصفوفة، 
• الخطوة رقم 1 تم تعيين القيمة الأولوية لهذا المتغير تساوي 1.
• الخطوة رقم 2 اذا كانت قيمة i اكبر من n (حجم المصفوفة) هذا يعني العنصر غير موجود. 
• الخطوة 3 نبدأ بالبحث عن القيمة x وذلك بمقارنة القيم في المصفوفة (A[i]) مع القيمة x. في حال تم العثور على العنصر يتم الانتقال الى الخطوة 6. وطباعة القيمة المطلوبة ثم انهاء العملية. 
• الخطوة رقم 4 اذا لم يتم العثور على القيمة المطلوبة في الخطوة السابقة يتم زيادة قيمة i بمقدار 1 للانتقال العنصر التالي.
• الخطوة رقم 5 إعادة تكرار العمليات السابقة من خطوة رقم 2 للوصول اما الى إيجاد العنصر او الانتهاء بعدم وجود العنصر. 

كود هذه الخوارزمية باستخدام لغة C 

اضف الكود التالي داخل ملف Notepad ثم قم بتشغيل الملف 

#include <stdio.h>
#define MAX 20
// array of items on which linear search will be conducted.
int intArray[MAX] = {1,2,3,4,6,7,9,11,12,14,15,16,17,19,33,34,43,45,50,55};
void printline(int count) {
   int i;
   for(i = 0;i < count-1;i++) {
      printf("=");
   }
   printf("=\n");
}
// this method makes a linear search. 
int find(int data) {
   int comparisons = 0;
   int index = -1;
   int i;
   // navigate through all items 
   for(i = 0;i < MAX;i++) {
      // count the comparisons made 
      comparisons++;
      // if data found, break the loop
      if(data == intArray[i]) {
         index = i;
         break;
      }
   }   
   printf("Total comparisons made: %d", comparisons);
   return index;
}
void display() {
   int i;
   printf("[");
   // navigate through all items 
   for(i = 0;i<MAX;i++) {
      printf("%d ",intArray[i]);
   }
   printf("]\n");
}
void main() {
   printf("Input Array: ");
   display();
   printline(14);

   //find location of 1
   int location = find(14);
   // if element was found 
   if(location != -1)
      printf("\nElement found at location: %d" ,(location+1));
   else
      printf("Element not found.");
}

النتيجة :

Input Array: [1 2 3 4 6 7 9 11 12 14 15 16 17 19 33 34 43 45 50 55 ]
==============
Total comparisons made: 10
Element found at location: 10

في هذه المثال المطلوب البحث عن القيمة 14 في المصفوفة : 

int intArray[MAX] = {1,2,3,4,6,7,9,11,12,14,15,16,17,19,33,34,43,45,50,65}

القيمة 14 موجودة في المكان رقم 10