This post is also available in: English (الإنجليزية) हिन्दी (الهندية)
في هذه المقالة ، سنناقش خمس خوارزميات بحث مهمة. تعد خوارزميات البحث والفرزجزءًا مهمًا من جميع التطبيقات تقريبًا. اقرأ المقال وأجب عن الأسئلة في اختبار في النهاية.
ما هي خوارزمية البحث؟
خوارزمية البحث هي إجراء خطوة بخطوة يستخدم لتحديد موقع بيانات محددة بين مجموعة من البيانات. يعتبر إجراء أساسي في الحوسبة. في علوم الكمبيوتر ، عند البحث عن البيانات ، غالبًا ما يكمن الاختلاف بين التطبيق السريع والتطبيق الأبطأ في استخدام خوارزمية البحث المناسبة.
تستخدم جميع خوارزميات البحث مفتاح البحث من أجل متابعة عملية البحث. من المتوقع أن تعيد خوارزميات البحث حالة النجاح أو الفشل ، وعادة ما يتم الإشارة إليها بواسطة Boolean true / false. تتوفر خوارزميات بحث مختلفة ، ويعتمد أداء وكفاءة هذه الخوارزميات على حجم البيانات وطريقة استخدامها.
العاملان الأساسيان المهمان بصرف النظر عن العديد من العوامل الأخرى التي يتم أخذها في الاعتبار عند اختيار أي خوارزمية هما الوقت والمكان. يجب أن تكون الخوارزمية بحيث تستغرق وقتًا أقل لتنفيذ المهمة (عامل الوقت) وأيضًا يجب أن تستخدم العملية الحد الأدنى من المساحة (عامل الفضاء).
أين يتم استخدام خوارزميات البحث؟
تعد خوارزميات البحث جزءًا مهمًا من أي تطبيق. عند إجراء مكالمة من هاتفك الخلوي ، يبحث البرنامج الموجود فيه عن رقم هاتف معين ويقوم بإجراء مكالمة. وبالمثل ، عندما تكتب اسمًا على منصة الوسائط الاجتماعية المفضلة لديك ، يبحث البرنامج عن هذا الاسم في قاعدة بياناته الضخمة. في الوقت الحاضر ، يعرف الجميع محركات البحث مثل Google و Bing وما إلى ذلك. تعد خوارزميات البحث جزءًا مهمًا من كل محركات البحث هذه. لا يمكننا التفكير في أي تطبيق لا يتم فيه استخدام خوارزميات البحث بشكل أو بآخر.
أنواع خوارزميات البحث
كما ذكر أعلاه ، هناك عاملان مهمان يتم أخذهما في الاعتبار عند اختيار الخوارزمية. اعتمادًا على متطلبات وحجم البيانات ، يتم تحديد خوارزمية بحث معينة لهذا الغرض. هنا سنناقش 5 خوارزميات البحث الهامة.
- البحث الخطي
- بحث ثنائي
- البحث السريع
- بحث الاستيفاء
- البحث الأسي
البحث الخطي
أول بحث في قائمة خوارزميات البحث المهمة هو البحث الخطي Linear Search. البحث الخطي هو خوارزمية بحث بسيطة للغاية. في هذا النوع من البحث ، يتم إجراء بحث تسلسلي على جميع العناصر واحدًا تلو الآخر. يتم فحص كل عنصر ، وإذا تم العثور على تطابق ، يتم إرجاع هذا العنصر المحدد ، وإلا ، يستمر البحث حتى نهاية جمع البيانات. إذا لم يتم العثور على العنصر حتى نهاية جمع البيانات ، تقوم الخوارزمية بإرجاع قيمة منطقية “خطأ” لم يتم العثور على عنصر المعنى.
كيف يعمل البحث الخطي؟
يتبع البحث الخطي الخطوات التالية:
- تهيئة المتغير المنطقي إلى خطأ.
- ابدأ من العنصر الموجود في أقصى اليسار (الأول) في المصفوفة وواحدًا تلو الآخر قارن العنصر الذي نبحث عنه مع كل عنصر في المصفوفة.
- إذا كان هناك تطابق بين العنصر الذي نبحث عنه والعنصر الحالي للمصفوفة ، فقم بإرجاع موضع العنصر وجعل المتغير المنطقي الموجود = صحيح.
- إذا وجدت = خطأ ، فلن يتم العثور على العنصر.
خوارزمية البحث الخطي
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
كود البحث الخطي في سي++
int search(int arr[], int n, int x)
{
int i;
for (i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
int main()
{
int arr[] = { 3, 4, 1, 7, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 4;
int index = search(arr, n, x);
if (index == -1)
cout << "Element is not present in the array";
else
cout << "Element found at position " << index;
return 0;
}
بحث ثنائي
البحث الثنائي هو خوارزمية مستخدمة على نطاق واسع للبيانات المصنفة ، وبالتالي فهي أخرى في قائمة خوارزميات البحث المهمة. البحث الثنائي هو نوع متقدم من خوارزمية البحث التي تبحث عن البيانات وجلبها من قائمة العناصر التي تم فرزها. يتضمن مبدأ عملها الأساسي تقسيم مجموعة البيانات في القائمة إلى نصفين حتى يتم تحديد العنصر المطلوب وإعادته. يُطلق أيضًا على البحث الثنائي أحيانًا البحث نصف الفاصل أو البحث اللوغاريتمي.
كيف يعمل البحث الثنائي؟
يتبع البحث الثنائي الخطوات التالية:
تبدأ عملية البحث عن طريق تحديد موقع العنصر الأوسط في مجموعة البيانات التي تم فرزها
- تهيئة المتغير المنطقي إلى خطأ.
- تتم مقارنة القيمة الرئيسية بالعنصر الحالي.
- إذا كانت قيمة المفتاح أكبر من العنصر الأوسط ، فسيحلل البحث القيم العليا للعنصر الأوسط للمقارنة والمطابقة.
- في حالة كانت قيمة المفتاح أصغر من العنصر الأوسط ، يقوم البحث بتحليل القيم الدنيا للعنصر الأوسط للمقارنة والمطابقة.
- في حالة تساوي قيمة المفتاح مع العنصر الأوسط ، أعد موضع العنصر الحالي ، واجعل المتغير المنطقي = صحيحًا.
- إذا وجدت = خطأ ، فلن يتم العثور على العنصر.
خوارزمية البحث الثنائي
Step 1: Set L to 0 and U to N and F to ‘False’
Step 2: MID = (L + U)/2
Step 3: if A[MID] = x, then Print Element x Found at index MID and set F to ‘True’ and goto step 6
Step 4: if A[MID] > x, U = MID – 1 and goto step 2
Step 5: if A[MID] < x, L = MID + 1 and goto step 2
Step 6: If F = ‘False’ then Print Element x Not Found
Step 7: Exit
رمز البحث الثنائي في ++C
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
البحث السريع
مثل البحث الثنائي ، يعد Jump Search خوارزمية بحث عن المصفوفات المصنفة. الفكرة الأساسية هي التحقق من عدد أقل من العناصر (من البحث الخطي) من خلال القفز إلى الأمام بخطوات ثابتة أو تخطي بعض العناصر بدلاً من البحث في جميع العناصر. هذا هو سبب احتلالها مكانًا في قائمة خوارزميات البحث المهمة
لنفكر في مصفوفة مرتبة A بالحجم n ، مع فهرس يتراوح من 0 إلى n-1 ، والعنصر x الذي يحتاج إلى البحث في المصفوفة A. لتنفيذ هذه الخوارزمية ، يلزم أيضًا كتلة بحجم m ، والتي يمكن أن تكون تخطي أو قفز في كل تكرار.
كيف يعمل البحث السريع؟
تعمل الخوارزمية على النحو التالي:
- Iteration 1: if x = A[0], then success, else if x > A[0], then jump to the next block.
- Iteration 2: if x = A[m], then success, else, if x > A[m], then jump to the next block.
- Iteration 3: if x = A[2m], then success, else, if x > Aw[2m], then jump to the next block.
- At any point in time, if x < A[km], then a linear search is performed from from position A[(k – 1)m] to A[km]
خوارزمية للبحث السريع
Step 1: Set i = 0 and m = sqrt(n).
Step 2: if A[i] != x and A[i] < x, then jump to the next block and set i = m and m = m + m.
Step 3: if m < n – 1 then goto step 2
Step 4: if A[i] > x, then move to the beginning of the current block and perform a linear search.
Step 5: Exit
رمز البحث السريع في ++C
int jumpSearch(int array[], int size, int key) {
int start = 0;
int end = sqrt(size);
while(array[end] <= key && end < size) {
start = end;
end += sqrt(size);
if(end > size - 1)
end = size;
}
for(int i = start; i<end; i++)
if(array[i] == key)
return i;
}
return -1;
}
int main() {
int n, searchKey, loc;
cout << "Enter number of items: ";
cin >> n;
int arr[n];
cout << "Enter items: " << endl;
for(int i = 0; i< n; i++) {
cin >> arr[i];
}
cout << "Enter search key to search in the list: ";
cin >> searchKey;
if((loc = jumpSearch(arr, n, searchKey)) >= 0)
cout << "Item found at location: " << loc << endl;
else
cout << "Item is not found in the list." << endl;
}
بحث الاستيفاء
يعد بحث الاستيفاء خوارزميات بحث مهمة أخرى. بحث الاستيفاءهو متغير محسّن للبحث الثنائي. تعمل خوارزمية البحث هذه على موضع فحص القيمة المطلوبة. لكي تعمل هذه الخوارزمية بشكل صحيح ، يجب أن يتم جمع البيانات في شكل فرز وتوزيع بالتساوي.
هناك حالات قد يكون فيها موقع بيانات الهدف معروفًا مسبقًا. على سبيل المثال ، في حالة دليل الهاتف ، إذا أردنا البحث في رقم هاتف شخص معين له اسم يبدأ بحرف “م”. هنا ، يبدو البحث الخطي وحتى البحث الثنائي بطيئًا حيث يمكننا الانتقال مباشرةً إلى مساحة الذاكرة حيث يتم تخزين الأسماء التي تبدأ من “M”.
في حالة البحث الثنائي ، إذا لم يتم العثور على البيانات المطلوبة ، فسيتم تقسيم بقية القائمة إلى جزأين ، أقل وأعلى. ثم يتم البحث في أي منهما. حتى إذا تم فرز البيانات ، فإن البحث الثنائي لا يستفيد من فحص موضع البيانات المطلوبة.
كيف يعمل بحث الاستيفاء؟
تعمل الخوارزمية على النحو التالي:
- يجد بحث الاستيفاء عنصرًا معينًا عن طريق حساب موضع التحقيق. في البداية ، يكون موضع الفحص هو موضع العنصر الوسيط للمجموعة.
- في حالة حدوث تطابق ، يتم إرجاع فهرس العنصر. لتقسيم القائمة إلى قسمين ، نستخدم الطريقة التالية:
mid = Lo + ((Hi – Lo)/(A[Hi] – A[Lo])) * (x – A[Lo]), where
A is list
Lo is lowest index of the list
Hi is highest index of the list
A[n] is the value stored at index n in the list
- إذا كان العنصر الأوسط أكبر من العنصر x ، فسيتم حساب موضع الفحص مرة أخرى في المصفوفة الفرعية على يمين العنصر الأوسط. خلاف ذلك ، يتم البحث عن العنصر في المصفوفة الفرعية الموجودة على يسار العنصر الأوسط. تستمر هذه العملية في المصفوفة الفرعية أيضًا حتى يقل حجم المصفوفة الفرعية إلى الصفر.
خوارزمية البحث عن الاستيفاء
Step 1: Start searching data from the middle of the list and initialize boolean variable F to ‘False’.
Step 2: If it is a match, return the index of the item and move ‘True’ to F goto
Step 3: If it is not a match, probe position.
Step 4: Divide the list using a probing formula and find the new middle.
Step 5: If the data is greater than middle, search in higher sub-list.
Step 6: If data is smaller than middle, search in lower sub-list.
Step 7: If F = ‘False’ then Print Element x Not Found
Step 8: Exit
كود البحث عن الاستيفاء في ++C
int interpolationSearch(int array[], int start, int end, int key) {
int dist, valRange, indexRange, estimate;
float fraction;
while(start <= end && key >= array[start] && key <= array[end]) {
dist = key - array[start];
valRange = array[end] - array[start];
fraction = dist / valRange;
indexRange = end - start;
estimate = start + (fraction * indexRange);
if(array[estimate] == key)
return estimate;
if(array[estimate] < key)
start = estimate +1;
else
end = estimate - 1;
}
return -1;
}
int main() {
int n, searchKey, loc;
cout << "Enter number of items: ";
cin >> n;
int arr[n];
cout << "Enter items: " << endl;
for(int i = 0; i< n; i++) {
cin >> arr[i];
}
cout << "Enter search key to search in the list: ";
cin >> searchKey;
if((loc = interpolationSearch(arr, 0, n-1, searchKey)) >= 0)
cout << "Item found at location: " << loc << endl;
else
cout << "Item is not found in the list." << endl;
}
البحث الأسي
التالي في قائمة خوارزميات البحث المهمة هو البحث الأسي. يُعرف البحث الأسي أيضًا باسم البحث المتضاعف أو الراكض. تُستخدم هذه الآلية للعثور على النطاق الذي قد يظهر فيه مفتاح البحث. إذا كان L و U هما الحدين السفلي والعلوي للقائمة ، فإن كلا من L و U هما أس 2. بالنسبة للقسم الأخير ، فإن U هي آخر موضع في القائمة. لهذا السبب ، يُعرف باسم الأسي. بعد العثور على النطاق المحدد ، يستخدم تقنية البحث الثنائي للعثور على الموقع الدقيق لمفتاح البحث.
خوارزمية البحث الأسي
Step 1: Jump the array 2^i elements at a time searching for the condition Array[2^(i-1)] < valueWanted < Array[2^i].
Step 2: If 2^i is greater than the length of the array, then set the upper bound to the length of the array.
Step 3: Do a binary search between Array[2^(i-1)] and Array[2^i]
رمز البحث الأسي في لغة ++C
int binarySearch(int array[], int start, int end, int key) {
if(start <= end) {
int mid = (start + (end - start) /2);
if(array[mid] == key)
return mid;
if(array[mid] > key)
return binarySearch(array, start, mid-1, key);
return binarySearch(array, mid+1, end, key);
}
return -1;
}
int exponentialSearch(int array[], int start, int end, int key){
if((end - start) <= 0)
return -1;
int i = 1;
while(i < (end - start)){
if(array[i] < key)
i *= 2;
else
break;
}
return binarySearch(array, i/2, i, key);
}
int main() {
int n, searchKey, loc;
cout << "Enter number of items: ";
cin >> n;
int arr[n];
cout << "Enter items: " << endl;
for(int i = 0; i< n; i++) {
cin >> arr[i];
}
cout << "Enter search key to search in the list: ";
cin >> searchKey;
if((loc = exponentialSearch(arr, 0, n, searchKey)) >= 0)
cout << "Item found at location: " << loc << endl;
else
cout << "Item is not found in the list." << endl;
}
Image Credit: Computer vector created by pch.vector – www.freepik.com
