أهلا بكم

سنتعلم فى هذا المقال كيفية استخدام خوارزمية البحث الثنائى مع الامثلة التوضيحية لعدة لغات برمجية

1_التعريف بالخوارزمية


خوارزمية البحث الثنائي (بالإنجليزية: Binary search algorithm)‏، المعروفة أيضًا باسم البحث المحدد بفاصل المنتصف، أو البحث اللوغاريتمي، هي خوارزمية بحث للعثور على موضع #index القيمة المستهدفة داخل مصفوفة مرتبة.

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

ملحوظة : لا يمكن استخدام تلك الخوارزمية فى حالة كون عناصر المصفوفة غير مرتبة فأنت بحاجة الى فرز أو ترتيب عناصر المصفوفة فى حالة كونها غير ذلك حتى تتمكن من البحث الثنائي للبحث عن موضع عنصر محدد.

2_كيف تعمل خوارزمية البحث الثنائى

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

• الخطوة 1: حدد أول عنصر و أخر عنصر بالمصفوفة
  
• الخطوة 2: ايجاد قيمة العنصر الأوسط في منتصف المصفوفة
  
• الخطوة 3: نقارن القيمة المستهدفة بالعنصر الأوسط في المصفوفة. إذا كان يتطابق مع العنصر الأوسط ، فسينتهي البحث هنا ولن يستمر أكثر من ذلك.
  
• الخطوة 4: وإلا إذا كان العنصر أقل من العنصر الأوسط ، فإننا نبدأ البحث في النصف السفلي من المصفوفة.
  
• الخطوة 5: وإلا إذا كان العنصر أكبر من العنصر الأوسط ، فإننا نبدأ البحث في النصف الأكبر من المصفوفة.
  
• الخطوة 6: سنكرر الخطوات 3 و 4 و 5 حتى يتم العثور على العنصر المستهدف.
  

3_تنفيذ الخوارزمية رياضيا :

إذا كانت  مصفوفة تحتوي على عنصر هي:  مرتبة ، وإذا كانت القيمة المُستهدَفة هي ، فبالإمكان العثور على مرتبة القيمة المُستهدَفة  في المصفوفة  على النحو التالى :


الخطوة 1 :تعين  و هما متغيران يمثلان موضع اقل و اكبر عنصر بالمصفوفة  اضبط قيمة  =  وقيمة =  بمعني حجم المصفوفة ناقص 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):
  
  
  
  
  •  القيمة المستهدفة 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):
  
  
  
  
  •  القيمة المستهدفة T و قمتها (23) تساوي قيمة الوسط (23) أذن أوقف البحث 
    
  
  
  
  4_تنفيذ الخوارزمية برمجيا : 
  
  يمكن تنفيذ خوارزمية البحث الثنائي بطريقتين كما هو موضح أدناه.
  
  
  
  
  1. الطريقة التكرارية Iterative Method
     
  2. الطريقة العودية 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);
  }
}

  09:19:42
  

@زهراء