خوارزمية البحث الثنائي Binary Search Algorithm
صفحة 1 من اصل 1 • شاطر
خوارزمية البحث الثنائي Binary Search Algorithm
أهلا بكم
سنتعلم فى هذا المقال كيفية استخدام خوارزمية البحث الثنائى مع الامثلة التوضيحية لعدة لغات برمجية
1_التعريف بالخوارزمية
خوارزمية البحث الثنائي (بالإنجليزية: Binary search algorithm)، المعروفة أيضًا باسم البحث المحدد بفاصل المنتصف، أو البحث اللوغاريتمي، هي خوارزمية بحث للعثور على موضع #index القيمة المستهدفة داخل مصفوفة مرتبة.
حيث يقارن البحث الثنائي القيمة المستهدفة بالعنصر المتوسط من المصفوفة. إذا لم تكن متساوية، يتم التخلص من النصف الذي لا يمكن للهدف أن يكون فيه ويستمر البحث في النصف المتبقي؛ تتكرر العملية مرة أخرى مع أخذ العنصر المتوسط للمقارنة بالقيمة المستهدفة، حتى العثور على القيمة المستهدفة. إذا كانت نتيجة البحث أن النصف المتبقي فارغ من العناصر، فهذا يعني أن القيمة المُستهدفة غير موجودة في المصفوفة.
ملحوظة : لا يمكن استخدام تلك الخوارزمية فى حالة كون عناصر المصفوفة غير مرتبة فأنت بحاجة الى فرز أو ترتيب عناصر المصفوفة فى حالة كونها غير ذلك حتى تتمكن من البحث الثنائي للبحث عن موضع عنصر محدد.
2_كيف تعمل خوارزمية البحث الثنائى
تعمل #خوارزمية البحث الثنائي وفقا للخطوات و التعليمات المنطقية والمتسلسلة التالية :
3_تنفيذ الخوارزمية رياضيا :
إذا كانت
مصفوفة تحتوي على
عنصر هي:
مرتبة ، وإذا كانت القيمة المُستهدَفة هي
، فبالإمكان العثور على مرتبة القيمة المُستهدَفة
في المصفوفة
على النحو التالى :
الخطوة 1 :تعين
و
هما متغيران يمثلان موضع اقل و اكبر عنصر بالمصفوفة اضبط قيمة
=
وقيمة
=
بمعني حجم المصفوفة ناقص 1
الخطوة 2: أوجد قيمة mid وهو متغير يمثل موضع منتصف المصفوفة ويمكن ايجادها باستخدام العلاقة المحسوبة التالية mid =
الخطوة 3: مقارنة القيمة المستهدفة T
أذن L=4+1=5 نعاود الذهاب للخطوة 2
أذن mid =(5+8)/2 =6
من المعادالة أعلاه رقم الفهرس index للعنصر الاوسط mid = 6 إذن قيمته فى المصفوفة = 20
4_قارن القيمة T المراد البحث عنها وقيمتها (23) بقيمة العنصر الاوسط mid فى المصفوفة و قيمته (20):
القيمة المستهدفة T و قمتها (23) أكبر من قيمة الوسط (20) أذن الحد الادنى لمصفوفة L =mid+1
أذن L=6+1=7 نعاود الذهاب للخطوة 2
أذن mid =(7+8)/2 =7
من المعادالة أعلاه رقم الفهرس index للعنصر الاوسط mid = 7 إذن قيمته فى المصفوفة = 23
4_قارن القيمة T المراد البحث عنها وقيمتها (23) بقيمة العنصر الاوسط mid فى المصفوفة و قيمته (23):
4_تنفيذ الخوارزمية برمجيا :
يمكن تنفيذ خوارزمية البحث الثنائي بطريقتين كما هو موضح أدناه.
التنفيذ بلغة السي C
التنفيذ بلغة السي ++ C
التنفيذ بلغة JAVA
التنفيذ بلغة السي C
التنفيذ بلغة السي ++ C
التنفيذ بلغة JAVA
سنتعلم فى هذا المقال كيفية استخدام خوارزمية البحث الثنائى مع الامثلة التوضيحية لعدة لغات برمجية
1_التعريف بالخوارزمية
خوارزمية البحث الثنائي (بالإنجليزية: Binary search algorithm)، المعروفة أيضًا باسم البحث المحدد بفاصل المنتصف، أو البحث اللوغاريتمي، هي خوارزمية بحث للعثور على موضع #index القيمة المستهدفة داخل مصفوفة مرتبة.
حيث يقارن البحث الثنائي القيمة المستهدفة بالعنصر المتوسط من المصفوفة. إذا لم تكن متساوية، يتم التخلص من النصف الذي لا يمكن للهدف أن يكون فيه ويستمر البحث في النصف المتبقي؛ تتكرر العملية مرة أخرى مع أخذ العنصر المتوسط للمقارنة بالقيمة المستهدفة، حتى العثور على القيمة المستهدفة. إذا كانت نتيجة البحث أن النصف المتبقي فارغ من العناصر، فهذا يعني أن القيمة المُستهدفة غير موجودة في المصفوفة.
ملحوظة : لا يمكن استخدام تلك الخوارزمية فى حالة كون عناصر المصفوفة غير مرتبة فأنت بحاجة الى فرز أو ترتيب عناصر المصفوفة فى حالة كونها غير ذلك حتى تتمكن من البحث الثنائي للبحث عن موضع عنصر محدد.
2_كيف تعمل خوارزمية البحث الثنائى
تعمل #خوارزمية البحث الثنائي وفقا للخطوات و التعليمات المنطقية والمتسلسلة التالية :
- الخطوة 1: حدد أول عنصر و أخر عنصر بالمصفوفة
- الخطوة 2: ايجاد قيمة العنصر الأوسط في منتصف المصفوفة
- الخطوة 3: نقارن القيمة المستهدفة بالعنصر الأوسط في المصفوفة. إذا كان يتطابق مع العنصر الأوسط ، فسينتهي البحث هنا ولن يستمر أكثر من ذلك.
- الخطوة 4: وإلا إذا كان العنصر أقل من العنصر الأوسط ، فإننا نبدأ البحث في النصف السفلي من المصفوفة.
- الخطوة 5: وإلا إذا كان العنصر أكبر من العنصر الأوسط ، فإننا نبدأ البحث في النصف الأكبر من المصفوفة.
- الخطوة 6: سنكرر الخطوات 3 و 4 و 5 حتى يتم العثور على العنصر المستهدف.
3_تنفيذ الخوارزمية رياضيا :
إذا كانت
الخطوة 1 :تعين
الخطوة 2: أوجد قيمة mid وهو متغير يمثل موضع منتصف المصفوفة ويمكن ايجادها باستخدام العلاقة المحسوبة التالية mid =
الخطوة 3: مقارنة القيمة المستهدفة T
- إذا كانت القيمة المستهدفة T أكبر من قيمة الوسط mid اضبط قيمة
إلى mid+1 ثُمَّّ انتقل إلى الخطوة 2.
- إذا كانت القيمة المستهدفة T أقل من قيمة الوسط mid اضبط قيمة
إلى mid-1 ثُمَّّ انتقل إلى الخطوة 2.
- وإلا، فإنَّ المساواة T تساوي mid أرجع قيمة mid، نهاية.
مثال توضيحيى :
نفترض أننا نريد البحث عن العنصر t و قيمتة 23 فى المصفوفة التالية :- الكود:
int a[]={1,5,7,8,13,19,20,23,29}
كل عنصر في المصفوفة له رقم فهرس index. يبدء من 0 وتتوقف عند نهاية المصفوفة وبالتالى فإن الفهارس لتلك المصفوفة ستكون على النحو التالى :- الكود:
Index: 0, 1, 2, 3, 4, 5, 6, 7, 8
Value: 1, 5, 7, 8, 13, 19, 20, 23, 29
1_قم بتعيين موضع أول و أخر عناصر المصفوفة :
أول عنصر رقم الفهرس index = 0
أخر عنصر رقم الفهرس index =8
و كقاعدة عامة أول عنصر بالمصفوفة قيمة الفهرس له = 0 و اخر عنصر بالمصفوفة =حجم المصفوفة - 1 أذن :
L = 0
R=A[].Len-1 =9-1=8
2_ايجاد قيمة العنصر الأوسط في منتصف المصفوفة باستخدام المعادلة التالية :mid =
أذن mid =(0+8)/2 =4
من المعادالة أعلاه رقم الفهرس index للعنصر الاوسط mid = 4 إذن قيمته فى المصفوفة = 13
3_قارن القيمة T المراد البحث عنها وقيمتها (23) بقيمة العنصر الاوسط mid فى المصفوفة و قيمته (13): - القيمة المستهدفة T و قمتها (23) أكبر من قيمة الوسط (13) أذن الحد الادنى لمصفوفة L =mid+1
أذن L=4+1=5 نعاود الذهاب للخطوة 2
أذن mid =(5+8)/2 =6
من المعادالة أعلاه رقم الفهرس index للعنصر الاوسط mid = 6 إذن قيمته فى المصفوفة = 20
4_قارن القيمة T المراد البحث عنها وقيمتها (23) بقيمة العنصر الاوسط mid فى المصفوفة و قيمته (20):
أذن L=6+1=7 نعاود الذهاب للخطوة 2
أذن mid =(7+8)/2 =7
من المعادالة أعلاه رقم الفهرس index للعنصر الاوسط mid = 7 إذن قيمته فى المصفوفة = 23
4_قارن القيمة T المراد البحث عنها وقيمتها (23) بقيمة العنصر الاوسط mid فى المصفوفة و قيمته (23):
- القيمة المستهدفة T و قمتها (23) تساوي قيمة الوسط (23) أذن أوقف البحث
4_تنفيذ الخوارزمية برمجيا :
يمكن تنفيذ خوارزمية البحث الثنائي بطريقتين كما هو موضح أدناه.
- الطريقة التكرارية Iterative Method
- الطريقة العودية Recursive Method
Iteration Method
- الكود:
function binary_search(A, n, T) is
L = 0
R = n − 1
while L ≤ R do
mid= ((L + R) / 2)
if A[mid] < T then
L = m + 1
else if A[mid] > T then
R = m - 1
else:
return mid
return unsuccessful
التنفيذ بلغة السي C
- الكود:
// Binary Search in C
#include <stdio.h>
int binarySearch(int array[], int T, int N) {
int L=0;
int R =N-1;
// Repeat until the pointers low and high meet each other
while (L <= R) {
int mid = (L + R) / 2;
if (array[mid] == T)
return mid;
if (array[mid] < T)
L = mid + 1;
else
R= mid - 1;
}
return -1;
}
int main(void) {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int n = sizeof(array) / sizeof(array[0]);
int T = 4;
int result = binarySearch(array, T, n );
if (result == -1)
printf("Not found");
else
printf("Element is found at index %d", result);
return 0;
}
التنفيذ بلغة السي ++ C
- الكود:
// Binary Search in C++
#include <iostream>
using namespace std;
int binarySearch(int arr[], int T) {
int L=0;
int N = sizeof(arr)/sizeof(arr[0]);
int R=N-1;
// Repeat until the pointers low and high meet each other
while (L <= R) {
int mid = (L + R) / 2;
if (arr[mid] == T)
return mid;
if (arr[mid] < T)
L = mid + 1;
else
R = mid - 1;
}
return -1;
}
int main(void) {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int T = 4;
int result = binarySearch(array, T);
if (result == -1)
std::cout << "Not found" << std::endl;
else
std::cout << "Element is found at index : "<< result ;
}
التنفيذ بلغة JAVA
- الكود:
// Binary Search in Java
class BinarySearch {
int binarySearch(int array[], int x, int low, int high) {
// Repeat until the pointers low and high meet each other
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == x)
return mid;
if (array[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int array[] = { 3, 4, 5, 6, 7, 8, 9 };
int n = array.length;
int x = 4;
int result = ob.binarySearch(array, x, 0, n - 1);
if (result == -1)
System.out.println("Not found");
else
System.out.println("Element found at index " + result);
}
}
Recursive Method
- الكود:
binarySearch(arr, x, low, high)
if low > high
return False
else
mid = (low + high) / 2
if x == arr[mid]
return mid
else if x < data[mid] // x is on the right side
return binarySearch(arr, x, mid + 1, high)
else // x is on the right side
return binarySearch(arr, x, low, mid - 1)
التنفيذ بلغة السي C
- الكود:
// Binary Search in C
#include <stdio.h>
int binarySearch(int array[], int x, int low, int high) {
if (high >= low) {
int mid = low + (high - low) / 2;
// If found at mid, then return it
if (array[mid] == x)
return mid;
// Search the left half
if (array[mid] > x)
return binarySearch(array, x, low, mid - 1);
// Search the right half
return binarySearch(array, x, mid + 1, high);
}
return -1;
}
int main(void) {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int n = sizeof(array) / sizeof(array[0]);
int x = 4;
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
printf("Not found");
else
printf("Element is found at index %d", result);
}
التنفيذ بلغة السي ++ C
- الكود:
// Binary Search in C++
#include <iostream>
using namespace std;
int binarySearch(int array[], int x, int low, int high) {
if (high >= low) {
int mid = low + (high - low) / 2;
// If found at mid, then return it
if (array[mid] == x)
return mid;
// Search the left half
if (array[mid] > x)
return binarySearch(array, x, low, mid - 1);
// Search the right half
return binarySearch(array, x, mid + 1, high);
}
return -1;
}
int main(void) {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int x = 4;
int n = sizeof(array) / sizeof(array[0]);
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
printf("Not found");
else
printf("Element is found at index %d", result);
}
التنفيذ بلغة JAVA
- الكود:
// Binary Search in Java
class BinarySearch {
int binarySearch(int array[], int x, int low, int high) {
if (high >= low) {
int mid = low + (high - low) / 2;
// If found at mid, then return it
if (array[mid] == x)
return mid;
// Search the left half
if (array[mid] > x)
return binarySearch(array, x, low, mid - 1);
// Search the right half
return binarySearch(array, x, mid + 1, high);
}
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int array[] = { 3, 4, 5, 6, 7, 8, 9 };
int n = array.length;
int x = 4;
int result = ob.binarySearch(array, x, 0, n - 1);
if (result == -1)
System.out.println("Not found");
else
System.out.println("Element found at index " + result);
}
}
زهراء- ........
- تاريخ التسجيل : 18/02/2011
المساهمات : 436
النقاط : 762
التقيم : 64
الدولة :
الجنس :
| |
صفحة 1 من اصل 1
صلاحيات هذا المنتدى:
لاتستطيع الرد على المواضيع في هذا المنتدى
» فوائد عشبة كف مريم للسحر
» مشكلة عند تشغيل الفيجوال بيسيك
» Pharmacy Retail System نظام إدارة الصيدليات بأستخدام VB.NET & SQL Server
» مشكلة بعد تستيب الفيجوال بيسيك
» كتابة برنامج ++C ...لحساب مجموع و المتوسط الحسابي لثلاثة ارقام
» كتابة برنامج ++C ...للتحقق مما إذا كان الرقم زوجيًا أو فرديًا باستخدام if...else
» حل نشاط Write a C++ function that takes a pointer to a string
» تعلم لغة البرمجة ++C... مقال 6_جمل التحكم البنائي ..1_الجمل الشرطية C++ if, if...else
» حل نشاط ++C...إنشاء مصفوفة ذات بعدين و التاكد من تساوي مجموعة صفوف و اعمدة المصفوفة