خوارزمية البحث الخطي Linear Search Algorithm
ما هي خوارزمية البحث الخطي Linear Search Algorithm…؟؟ وأين تصنف خوارزمية البحث الخطي Linear Search Algorithm بين خوارزميات البحث ..؟؟!! ما هي خصائص خوارزمية البحث الخطي Linear Search Algorithm …؟؟؟!! وأين يمكن تطبيق خوارزمية البحث الخطي Linear Search Algorithm لتعمل بشكل فعال...؟!!
خوارزمية البحث الخطي (Linear Search Algorithm) هي واحدة من أبسط وأسهل الخوارزميات التي تستخدم للبحث عن قيمة محددة في مجموعة متسلسلة من العناصر. في هذا المقال، سنستكشف خوارزمية البحث الخطي Linear Search Algorithm بشكل مفصل. سنتعرف على كيفية تنفيذها، ونقدم أمثلة لتوضيح عملية البحث الخطي. سنناقش أيضًا تعقيد الخوارزمية ونقدم بعض النصائح لاستخدامها بكفاءة. لنبدأ…
في هذا المقال نتعرف على:
- خوارزميات البحث Search Algorithms.
- ما هي خوارزمية البحث الخطي (Linear Search).
- تحليل خوارزمية البحث الخطي Linear Search.
- خصائص خوارزمية البحث الخطي Linear Search.
- تطبيقات البحث الخطي Linear Search.
خوارزميات البحث Search Algorithms
في البرمجة تتعامل مشكلة البحث مع إيجاد قيمة معينة، تسمى مفتاح البحث، في مجموعة معينة (أو مجموعة متعددة، والتي تسمح لعدة عناصر بأن يكون لها نفس القيمة). هناك الكثير من خوارزميات ومن بينها :
- البحث الخطي Linear Search أو مايعرف بالبحث المتسلسل ( Sequential Search).
- البحث الثنائي(Binary Search) .
بالنسبة للبحث، لا توجد خوارزمية واحدة تناسب جميع حالات بشكل أفضل. تعمل بعض الخوارزميات بشكل أسرع من غيرها ولكنها تتطلب ذاكرة أكبر؛ بعضها سريع جدًا ولكنه ينطبق فقط على المصفوفات المرتبة. على عكس خوارزميات الفرز و الترتيب (Sorting Algorithms)، لا توجد مشكلة في الاستقرار، ولكن تظهر مشاكل مختلفة.
و في التطبيقات التي قد تتغير فيها البيانات الأساسية بشكل متكرر بالنسبة لعدد عمليات البحث، يجب النظر في البحث جنبًا إلى جنب مع عمليتين أخريين هما الإضافة إلى مجموعة البيانات بعنصر ما والحذف منها. في مثل هذه الحالات، ينبغي اختيار هياكل البيانات والخوارزميات لتحقيق التوازن بين متطلبات كل عملية. كما أن تنظيم مجموعات بيانات كبيرة جدًا للبحث الفعال يفرض تحديات خاصة لها آثار مهمة على تطبيقات العالم الحقيقي.
ما هي خوارزمية البحث الخطي (Linear Search)
خوارزمية البحث الخطي Linear Search هي خوارزمية بسيطة تستخدم للبحث عن قيمة محددة في مجموعة متسلسلة من البيانات لهذا تسمى هذه الخوارزمية بالبحث المتسلسل Sequential Search. وتعتبر الخوارزمية البحث المتسلسل أحد الأساليب الأساسية للبحث وتعمل عن طريق فحص كل عنصر في بشكل تتابعي من البداية إلى النهاية حتى يتم العثور على القيمة المطلوبة أو حتى يتم استكمال فحص جميع العناصر.
تعتبر خوارزمية البحث الخطي Linear Search النوع الأكثر وضوحًا للبحث حيث تبدأ من بداية مجموعة البيانات وتقارن كل عنصر من العناصر مع القيمة المراد البحث عنها وتتوقف في حالتين اما الوصول الى قيمة مطابقة للقيمة المبحوث عنها أو الوصول الى نهاية مجموعة البيانات .
وتتبع خوارزمية البحث الخطي Linear Search عدة خطوات بسيطة:
- تحديد القيمة المستهدفة: يتم تحديد القيمة التي نرغب في البحث عنها في مجموعة متسلسلة من البيانات .
- التصفح التتابعي: يتم فحص كل عنصر في المجموعة واحدًا تلو الآخر بدءًا من العنصر الأول حتى العنصر الأخير.
- المقارنة: يتم مقارنة كل عنصر في المجموعة بالقيمة المستهدفة للبحث.
- العثور على التطابق: في حالة وجود تطابق بين القيمة المستهدفة والعنصر الحالي، يتم إعلان العثور على القيمة وإرجاع موقعها أو العنصر نفسه.
- عدم العثور على التطابق: في حالة عدم العثور على التطابق بين القيمة المستهدفة وأي من العناصر في المجموعة يتم إشعار المستخدم بذلك أو إرجاع قيمة تشير إلى عدم وجود التطابق.
تُعد خوارزمية البحث الخطي (Linear Search) واحدة من أبسط وأسهل الخوارزميات المستخدمة في علوم الحاسوب. يتم استخدامها للبحث عن قيمة محددة داخل مجموعة متسلسلة من البيانات، سواء كانت مصفوفة (Array) أو قائمة (List) أو أي هيكلة بيانات أخرى. وتتضح طريقة عمل خوارزمية البحث الخطي (Linear Search) في الشكل التالي:
أي تقوم خوارزمية البحث الخطي Linear Search ببساطة بمقارنة العناصر المتعاقبة لقائمة معينة مع مفتاح بحث معين حتى يتم العثور على تطابق (بحث ناجح - Successful search) أو استنفاد القائمة دون العثور على تطابق (بحث غير ناجح - Unsuccessful search). كما يتضح في الأمثلة التالية:
وتكتب خوارزمية البحث الخطي Linear Search على النحو التالي :
ALGORITHM SequentialSearch2(A[0..n], K)
//Implements sequential search with a search key as a sentinel
//Input: An array A of n elements and a search key K
//Output: The index of the first element in A[0..n − 1] whose value is
// equal to K or −1 if no such element is found A[n]←K
i ←0
while A[i] = K do
i ←i + 1
if i < n return i
else return −1
وفيما يلي تطبيق لخوارزمية البحث الخطي Linear Search من خلال لغات برمجة مختلفة
تطبيق خوارزمية البحث الخطي Linear Search في لغة C:
#include <stdio.h>
int linearSearch(int arr[], int target);
int main()
{
int A[] = {13,20,10,35,70,9};
printf("%d\n",linearSearch(A, 35));
printf("%d\n",linearSearch(A, 50));
return 0;
}
int linearSearch(int arr[], int target){
int n = sizeof(arr);
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
تطبيق خوارزمية البحث الخطي Linear Search في لغة Python:
def linearSearch(listNum, target):
i =0
while i < len(listNum):
if listNum[i] == target:
return i
i= i+1
return -1
print(linearSearch([13,20,10,35,70,9] , 35))
print(linearSearch([13,20,10,35,70,9] , 50))
تطبيق خوارزمية البحث الخطي Linear Search في لغة JavaScript :
function linearSearch(arr, target) {
let n = arr.length;
for (let i = 0; i < n; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}
let A = [13,20,10,35,70,9];
console.log(linearSearch(A, 35));
console.log(linearSearch(A, 50));
خوارزمية البحث الخطي Linear Search تعمل بشكل جيد للبيانات الصغيرة أو عندما لا يتطلب البحث ترتيبًا محددًا للعناصر. ومع ذلك، يجب ملاحظة أنها ليست الأكثر كفاءة عند التعامل مع بيانات كبيرة، حيث قد يستغرق البحث وقتًا طويلاً في حالة وجود القيمة في العنصر الأخير أو عندما يتكرر البحث عدة مرات في نفس القائمة. في مثل هذه الحالات، يفضل استخدام خوارزميات البحث الأكثر تطورًا مثل البحث الثنائي (Binary Search) أو تقنيات الهاش (Hashing) التي توفر أداءً أفضل.
تحليل خوارزمية البحث الخطي Linear Search
إن تعقيد خوارزمية البحث الخطي Linear-search يشير إلى كمية الوقت والموارد التي تحتاجها الخوارزمية لإتمام عملية البحث في مجموعة من العناصر (المزيد في مقال عن كفاءة الخوارزميات ) . يتم قياس تعقيد الوقت بناءً على عدد المقارنات التي يقوم بها الخوارزمية، بينما يتم قياس تعقيد المساحة بناءً على الذاكرة الإضافية التي تحتاجها الخوارزمية لتنفيذ العملية. فيكون التعقيد لخوارزمية البحث الخطي Linear-search يكون كالتالي:
تعقيد الوقت Time Complexity : في أسوأ الحالات (Worse case )، عندما يكون العنصر المطلوب غير موجود في عناصر المجموعة أو يكون موجودًا في نهايته، يجب أن يتم فحص كل العناصر في المجمووعة. مما يتطلب عددًا من المقارنات بحسب عدد العناصر في المجموعة. بالتالي,يكون التعقيد الزمني للبحث الخطي هو O(n)، حيث n هو عدد العناصر في المجموعة.
تعقيد المساحة Space Complexity : تعتمد تعقيد المساحة للبحث الخطي على طريقة تخزين المجموعة في الذاكرة. إذا كان لدينا مصفوفة أو قائمة تحتفظ بجميع العناصر، فإن تعقيد المساحة سيكون O(n)، حيث n هو عدد العناصر في المجموعة. وذلك لأنه يتم تخزين جميع العناصر في الذاكرة. ومع ذلك، إذا كان لدينا فقط متغيرين لتتبع المؤشر على العنصر الحالي والقيمة المستهدفة، فإن تعقيد المساحة سيكون O(1)، حيث يتم استخدام ذاكرة ثابتة للمتغيرات فقط.
يجب مراعاة أن التعقيد هنا يشير إلى أسوأ الحالات (Worse case )، حيث يتم البحث عن العنصر في أقصى الحالات التي تحتاج إلى التحقق من جميع العناصر. في حالة العثور على العنصر في وسط المجموعة أو في البداية، يمكن أن يكون التعقيد أقل من O(n) ولكنه لا يتجاوز O(n).
بشكل عام، تعتبر خوارزمية البحث الخطي Linear Search خوارزمية بسيطة وسهلة التنفيذ، ولكنه قد تكون غير فعالة في حالة التعامل مع مجموعة ضخمة من البيانات أو تكرار البحث عدة مرات. في تلك الحالات، يكون من الأفضل استخدام خوارزميات البحث الأكثر كفاءة مثل البحث الثنائي (Binary search) أو هياكل بيانات أخرى مثل الجداول المفتوحة (Hash tables) أو الأشجار (Trees) لتحسين أداء البحث.
خصائص خوارزمية البحث الخطي Linear Search
فيما يلي بعض خصائص خوارزمية البحث الخطي Linear Search :
- البساطة وسهولة التنفيذ: يعد البحث الخطي أحد أبسط الخوارزميات التي يمكن فهمها وتنفيذها. أنها تنطوي على هياكل حلقة أساسية وعبارات شرطية، مما يجعلها في متناول حتى للمبتدئين في البرمجة أو علوم الكمبيوتر. منطقها المباشر يجعلها نقطة انطلاق جيدة للتعرف على خوارزميات البحث.
- كفاءة الذاكرة: لا يتطلب البحث الخطي أي ذاكرة إضافية أو هياكل بيانات تتجاوز حجم البيانات الأصلي الذي يتم البحث فيه. يقوم بالبحث مباشرة على البيانات المعطاة، مما يقلل من استخدام الذاكرة. وهذا يجعله خيارًا عمليًا في الحالات التي تكون فيها قيود الذاكرة مصدر قلق.
- التعقيد الزمني (Time Complexity) : التعقيد الزمني للبحث الخطي هو O(n)، حيث يمثل 'n' عدد العناصر في مجموعة البيانات. وهذا يعني أن الوقت المستغرق لإجراء البحث يزداد مع حجم البيانات. في أسوأ السيناريوهات، عندما تكون القيمة المطلوبة في نهاية المجموعة أو غير موجودة على الإطلاق، سيتعين على تكرار الخوارزمية المرور عبر جميع العناصر.
- البيانات غير المرتبة: البحث الخطي فعال للبحث في البيانات غير المرتبة أو غير المصنفة. نظرًا لأنه يتحقق من كل عنصر واحدًا تلو الآخر، فهو لا يعتمد على أي ترتيب أو ترتيب محدد للبيانات. وهذا يجعلها مناسبة للسيناريوهات التي لا يتم فيها تنظيم البيانات أو عندما لا يكون الترتيب معروفًا مسبقًا.
- الوصول المتسلسل: يتبع البحث الخطي نمط وصول متسلسل، حيث يقوم بفحص كل عنصر من البداية إلى النهاية حتى يتم العثور على تطابق أو الوصول إلى نهاية المجموعة. هذه الخاصية تجعلها مناسبة لهياكل البيانات التي تدعم الوصول المتسلسل، مثل المصفوفات (Arrays) أو القوائم المرتبطة (Linked-List).
- تكرارات متعددة: يمكن للبحث الخطي التعامل مع المواقف التي تحدث فيها القيمة المطلوبة عدة مرات ضمن مجموعة البيانات. سيجد التواجد الأول الذي تمت مواجهته أثناء عملية البحث. إذا كانت هناك حاجة للعثور على كافة التكرارات، فيمكن تنفيذ منطق إضافي لتسجيل كل مثيل أو حسابه.
إن البحث الخطي (Linear-search) هو خوارزمية أساسية ومباشرة للبحث عن القيم ضمن مجموعة متسلسلة من البيانات. وهو مناسب أكثر لمجموعات البيانات الصغيرة أو غير المرتبة حيث يتم إعطاء الأولوية للبساطة وسهولة التنفيذ على كفاءة البحث. يعد فهم مبادئها وقيودها أمرًا ذا قيمة لبناء أساس في علوم الكمبيوتر والتفكير الخوارزمي. ومع ذلك، بالنسبة لمجموعات البيانات الأكبر أو المرتبة، ينبغي النظر في خوارزميات البحث البديلة لتحسين الأداء.
تطبيقات البحث الخطي Linear search
يمكن استخدام خوارزمية البحث الخطي (Linear search) في العديد من التطبيقات حيث نحتاج إلى البحث عن قيمة معينة في مجموعة من العناصر. ومن بين الأمثلة الشائعة على استخدام خوارزمية البحث الخطي Linear search:
- البحث في قوائم غير مرتبة: عندما يكون لدينا قائمة من العناصر غير مرتبة ونرغب في العثور على قيمة محددة في هذه القائمة، يمكن استخدام البحث الخطي.
- التحقق من وجود عنصر معين: قد يكون لدينا مجموعة من العناصر ونرغب في التحقق مما إذا كان عنصر معين موجودًا في المجموعة أم لا.في هذه الحالة يمكن استخدام البحث الخطي للتحقق من وجود هذا العنصر.
- البحث عن أكبر Maximum وأصغر Minimum قيمة: في بعض الأحيان، نحتاج إلى البحث عن أكبر قيمة أو أصغر قيمة في مجموعة بيانات معينة. يمكن استخدام البحث الخطي لتحقيق ذلك عن طريق مقارنة القيم بينها.
- البحث في مجموعة بيانات غير معروف الحجم: إذا كان لدينا مجموعة بيانات غير معروفة الحجم أو غير مؤشر عليه، يمكن استخدام البحث الخطي للتحقق من وجود قيمة معينة في المجموعة.
إن استخدام خوارزمية البحث الخطي Linear search عندما يكون حجم البيانات صغيرًا أو عندما يكون البحث نادر الحدوث. إذا كان لديك مجموعة بيانات متسلسلة كبيرة أو مرتبة، فمن الأفضل استخدام خوارزميات البحث الأكثر كفاءة من البحث الخطي.
في الخاتم، نستنتج أن خوارزمية البحث الخطي Linear-Search تعتبر واحدة من الأساليب البسيطة والفعالة للبحث عن قيمة محددة في مجموعة متسلسلة من العناصر. على الرغم من بساطتها، إلا أنها تستخدم على نطاق واسع في البرمجة وتوفر طريقة سهلة للتحقق من وجود أو عدم وجود عنصر في المجموعات الصغيرة. سواء كنت مبتدئًا في علوم الكمبيوتر أو محترفًا، ستجد في هذا المقال معلومات قيمة حول خوارزمية البحث الخطي (Linear Search) وكيفية استخدامها في العديد من السيناريوهات.