البحث الخطي: 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) يتوقف.

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

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

تُجسّد الشفرة الزائفة التالية منطق البحث الخطي الموصوف أعلاه. فهي تتنقل عبر المصفوفة بدءًا من الفهرس الأول، وتُعيد موضع العنصر عند العثور على تطابق، وإلا فإنها تُعيد القيمة -1.

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 a negative index is not valid
    return -1

C++ Code مثال للبحث الخطي

وهنا كامل 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(array[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(array, 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 Code مثال للبحث الخطي

المنطق نفسه في 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) قم بتبديل data[5] و data[4]. عندها سيصبح شكل مصفوفة البيانات كالتالي:

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

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

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

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

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

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

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

الأسئلة الشائعة