البحث الخطي: Python, C++ مثال

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

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

ما هو البحث الخطي؟

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

ماذا تفعل وظيفة البحث الخطي؟

يتم إعطاء مجموعة من الأعداد الصحيحة كـ "Numbers"، ويحتوي "العنصر" المتغير على الرقم الصحيح المطلوب البحث فيه.

الآن، يمكن لخوارزمية البحث الخطي توفير الناتج التالي:

• "-1"؛ هذا يعني أن العنصر المحدد غير موجود في المصفوفة
• أي رقم بين 0 إلى n-1؛ يعني أنه تم العثور على عنصر البحث، ويقوم بإرجاع فهرس العنصر الموجود في المصفوفة. هنا يمثل "n" حجم المصفوفة.

كيف يعمل البحث الخطي؟

لنفترض أن لدينا مصفوفة تحتوي على أعداد صحيحة. المهمة هي العثور على رقم معين في المصفوفة.

• إذا كان الرقم موجودًا في المصفوفة، فسنحتاج إلى إرجاع فهرس هذا الرقم.
• إذا لم يتم العثور على الرقم المحدد، فسوف يعود -1.

في المخطط الانسيابي، "البيانات" هي المصفوفة الصحيحة، و"N" هو حجم المصفوفة، و"العنصر" هو الرقم الذي نريد البحث عنه في المصفوفة.

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

فيما يلي خطوات المخطط الانسيابي:

الخطوة 1) اقرأ عنصر البحث "عنصر".

الخطوة 2) ابدأ i=0 وindex=-1

الخطوة 3) اذا انا

الخطوة 4) إذا كانت البيانات [i] تساوي "العنصر"، فانتقل إلى الخطوة 5. وإلا فانتقل إلى الخطوة 6.

الخطوة 5) الفهرس = i (حيث أن العنصر موجود في الفهرس رقم i). انتقل إلى الخطوة 8.

الخطوة 6) أنا = أنا +1.

الخطوة 7) انتقل إلى الخطوة 3.

الخطوة 8) يتوقف.

من أجل التبسيط، نقدم مثالا مع مجموعة من الأعداد الصحيحة. البحث الخطي قابل للتطبيق أيضًا في السلسلة أو مجموعة الكائنات أو البنية.

الكود الزائف لخوارزمية البحث التسلسلي

function linearSearch: in →Data[], item
foundAt = -1
for i in (0 to data.length): if data[i] equals item
// item is found in the array
// returning the index
return i
// item not found in the array
// -1 means no item found, as negative index is not valid
return -1

C++ رمز مثال البحث الخطي

#include < bits / stdc++.h >
    using namespace std;
int linearSearch(int * arr, int item, int n) {
    int idx = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] == item) {
            idx = i;
            break;
        }
    }
    return idx;
}
int main() {
    int array[] = {
        1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10
    };
    int n = sizeof(array) / sizeof(arr[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(arr, item, n);
    if (idx >= 0) {
        cout << item << " is found at index " << idx << endl;
    } else {
        cout << "Could not find " << item << " in the array" << endl;
    }
}

الإخراج:

Enter a number to search: -10
-10 is found at index 14

Python رمز مثال البحث الخطي

def linearSearch(data, item):
    for i in range(len(data)):
    if data[i] == item:
    return i
return -1
data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10]
item = int(input("Enter a number to search: "))
idx = linearSearch(data, item)
if idx >= 0:
    print("{} is found at index {}".format(item, idx))
else :
    print("{} was not found".format(item))

الإخراج:

Enter a number to search: -10
-10 is found at index 14

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

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

هناك ثلاثة أنواع من التعقيدات الزمنية:

• السيناريو الأسوأ
• أفضل سيناريو الحالة
• متوسط ​​سيناريو الحالة

التعقيد الزمني للبحث الخطي في أسوأ سيناريو:

لنفترض أننا بحاجة إلى إجراء بحث خطي في مصفوفة بحجم "n". يمكننا العثور على عنصر البحث بين الفهرس 0 إلى n-1. في أسوأ السيناريوهات، ستحاول الخوارزمية مطابقة جميع العناصر من المصفوفة مع عنصر البحث.

في هذه الحالة، سيكون أسوأ تعقيد هو O(n). هنا، يشير تدوين "O"-big O إلى دالة التعقيد.

التعقيد الزمني للبحث الخطي في أفضل سيناريو:

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

التعقيد الزمني للبحث الخطي في سيناريو الحالة المتوسط:

عندما يتم العثور على عنصر في المؤشر الأوسط للمصفوفة، فيمكن القول أن متوسط ​​تعقيد الحالة للبحث الخطي هو O(N)، حيث يعني N طول المصفوفة.

تعقيد الفضاء لخوارزمية البحث الخطي

تكون تعقيدات المساحة للبحث الخطي دائمًا O(N) لأننا لا نحتاج إلى تخزين أو استخدام أي نوع من المتغيرات المؤقتة في دالة البحث الخطية.

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

يمكن إجراء البحث عدة مرات طوال دورة حياة البرنامج. ومن الممكن أيضًا أن نقوم بتشغيل خوارزمية البحث الخطي والبحث عن أي مفتاح محدد عدة مرات. يمكننا استخدام "خوارزمية البحث الثنائية"إذا كانت المصفوفة عبارة عن مصفوفة مرتبة.

افترض أن المصفوفة تتكون من 10 آلاف رقم، وأن العنصر المستهدف موجود عند الفهرس رقم 5000. لذا، ستحاول الخوارزمية مقارنة 5000 عنصر. الآن، المقارنات هي مهام تعتمد على وحدة المعالجة المركزية بشكل كبير. لتحسين خوارزمية البحث الخطي، لدينا خياران.

• التحويل
• تحرك إلى الأمام

التحويل:

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

البيانات[] = {1,5,9,8,7,3,4,11}

والآن نريد البحث 4. خطوات النقل:

الخطوة 1) تم العثور على "4" في الفهرس 6. واستغرق الأمر ست مقارنات.

الخطوة 2) مبادلة البيانات[6] والبيانات[5]. ثم ستبدو مصفوفة البيانات كما يلي:

البيانات[] = {1,5,9,8,7,4,3,11}

الخطوة 3) بحث 4 مرة أخرى. تم العثور عليه في الفهرس 5. هذه المرة استغرق الأمر خمس مقارنات.

الخطوة 4) مبادلة البيانات [5] والبيانات [4]. ثم ستبدو مصفوفة البيانات كما يلي:

البيانات [] = {1,5,9,8,4,7,3,11}

الآن، إذا لاحظت أنه كلما زاد تكرار البحث عن المفتاح، زاد انخفاض الفهرس. وبالتالي تقليل عدد المقارنات.

الانتقال إلى الأمام:

في هذه الطريقة نقوم بتبديل عنصر البحث في الفهرس 0. لأنه إذا تم البحث عنه مرة أخرى، فيمكننا العثور عليه في الوقت O(1).

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

فيما يلي بعض تطبيقات البحث الخطي التي يمكننا استخدامها.

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