بحث خطي

البحث الخطي أو البحث المتسلسل (بالإنجليزية: Liner search)‏ في علوم الحاسوب، هي طريقة لإيجاد قيمة في مجموعة أو قائمة والبحث يكون بفحص كل قيم المجموعة أو القائمة واحدا تلو الآخر حتى إيجاد القيمة المطلوبة أو انتهاء القائمة.[1] البحث الخطي ما هو إلا حالة خاصة من خوارزمية أعم وهي خوارزمية البحث الشامل. بما أن البحث الخطي لا يفترض أي افتراضات قوية بشكل عام هنالك خورزميات يمكن أن تكون أفضل مثل خوارزمية البحث الثنائي أو دالة هاش.

الخوارزمية وتحليلها

زمن الفعالية المفترضة للخوارزمية في اسوأ الحالات هي (O(N حيث أن N هو كبر المجموعة

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

رقم الخانة 0 1 2 3 4 5 6 7 8 9 10
المصفوفة 05131922415568728198

طول المصفوفة يساوي 11 A.Length=11 ,

[A[i حيث نعني i هو الفهرس و A هي المصفوفة التي تحتوي على العناصر

هل A[i]=A[0]=0 تساوي العدد الذي نبحث عنه وهو 55 طبعا لا

هل A[1]=5 تساوي العدد الذي نبحث عنه وهو 55 طبعا لا

هل A[2]=13 تساوي العدد الذي نبحث عنه وهو 55 طبعا لا

هل A[3]=19 تساوي العدد الذي نبحث عنه وهو 55 طبعا لا

هل A[4]=22 تساوي العدد الذي نبحث عنه وهو 55 طبعا لا

هل A[5]=41 تساوي العدد الذي نبحث عنه وهو 55 طبعا لا

هل A[6]=55 تساوي العدد الذي نبحث عنه وهو 55 طبعا وهنا سوف يتوقف البحث لاننا وجدنا العنصر الذي نبحث عنه

الخوارزمية التي تعبر عن ذلك هي :

Int i=0;
Boolean found=false;
While(i<A.Length&&!found){
If(item==A[i])
Found=true;
I++;
}

مراجع

  1. "معلومات عن بحث خطي على موقع aleph.nkp.cz"، aleph.nkp.cz، مؤرشف من الأصل في 13 ديسمبر 2019.


  • بوابة علم الحاسوب
  • بوابة تقنية المعلومات
  • بوابة خوارزميات
  • بوابة تقانة
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.