منتدى مصر التقني
هل تريد التفاعل مع هذه المساهمة؟ كل ما عليك هو إنشاء حساب جديد ببضع خطوات أو تسجيل الدخول للمتابعة.

خوارزمية البحث الثنائي Binary Search Algorithm

اذهب الى الأسفل

خوارزمية البحث الثنائي  Binary Search Algorithm Empty خوارزمية البحث الثنائي Binary Search Algorithm

مُساهمة من طرف زهراء الجمعة يناير 22, 2021 9:42 am

أهلا بكم

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

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


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

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

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

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

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


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



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

إذا كانت خوارزمية البحث الثنائي  Binary Search Algorithm 7daff47fa58cdfd29dc333def748ff5fa4c923e3 مصفوفة تحتوي علىخوارزمية البحث الثنائي  Binary Search Algorithm A601995d55609f2d9f5e233e36fbe9ea26011b3b عنصر هي: خوارزمية البحث الثنائي  Binary Search Algorithm 6d8d813e3e6d50ef13e04948e72fcacaf43b7d5c مرتبة ، وإذا كانت القيمة المُستهدَفة هي خوارزمية البحث الثنائي  Binary Search Algorithm Ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0، فبالإمكان العثور على مرتبة القيمة المُستهدَفة خوارزمية البحث الثنائي  Binary Search Algorithm Ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0 في المصفوفة خوارزمية البحث الثنائي  Binary Search Algorithm 7daff47fa58cdfd29dc333def748ff5fa4c923e3 على النحو التالى :


الخطوة 1 :تعين خوارزمية البحث الثنائي  Binary Search Algorithm 103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8 وخوارزمية البحث الثنائي  Binary Search Algorithm 4b0bfb3769bf24d80e15374dc37b0441e2616e33 هما متغيران يمثلان موضع اقل و اكبر عنصر بالمصفوفة  اضبط قيمة خوارزمية البحث الثنائي  Binary Search Algorithm 103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8 = خوارزمية البحث الثنائي  Binary Search Algorithm 2aae8864a3c1fec9585261791a809ddec1489950 وقيمة خوارزمية البحث الثنائي  Binary Search Algorithm 4b0bfb3769bf24d80e15374dc37b0441e2616e33خوارزمية البحث الثنائي  Binary Search Algorithm Fbd0b0f32b28f51962943ee9ede4fb34198a2521 بمعني حجم المصفوفة ناقص 1


الخطوة 2: أوجد قيمة mid وهو متغير يمثل موضع منتصف المصفوفة ويمكن ايجادها باستخدام العلاقة المحسوبة التالية mid =خوارزمية البحث الثنائي  Binary Search Algorithm Ed7e052f47e5069015943e2ad3c12363ac155250


الخطوة 3: مقارنة القيمة المستهدفة T


  • إذا كانت القيمة المستهدفة  T أكبر من قيمة الوسط mid اضبط قيمة خوارزمية البحث الثنائي  Binary Search Algorithm 103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8 إلى mid+1 ثُمَّّ انتقل إلى الخطوة 2.

  • إذا كانت القيمة المستهدفة  T أقل من قيمة الوسط mid اضبط قيمة خوارزمية البحث الثنائي  Binary Search Algorithm 103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8 إلى 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 =خوارزمية البحث الثنائي  Binary Search Algorithm Ed7e052f47e5069015943e2ad3c12363ac155250     

    أذن mid =(0+8)/2 =4

    خوارزمية البحث الثنائي  Binary Search Algorithm 672645456

    من المعادالة أعلاه رقم الفهرس 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
  • خوارزمية البحث الثنائي  Binary Search Algorithm 317015759

    من المعادالة أعلاه رقم الفهرس 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

    خوارزمية البحث الثنائي  Binary Search Algorithm 228836875

    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
زهراء
زهراء
........
........

تاريخ التسجيل : 18/02/2011
المساهمات : 436
النقاط : 763
التقيم : 65
الدولة : مصر
الجنس : انثى

الرجوع الى أعلى الصفحة اذهب الى الأسفل

خوارزمية البحث الثنائي  Binary Search Algorithm Empty رد: خوارزمية البحث الثنائي Binary Search Algorithm

مُساهمة من طرف vbcoder الجمعة نوفمبر 19, 2021 8:34 am

vbcoder
vbcoder
...
...

تاريخ التسجيل : 18/11/2018
المساهمات : 49
النقاط : 79
التقيم : 4
الدولة : مصر
الجنس : ذكر

الرجوع الى أعلى الصفحة اذهب الى الأسفل

الرجوع الى أعلى الصفحة

ََ

مواضيع ذات صلة


 
صلاحيات هذا المنتدى:
لاتستطيع الرد على المواضيع في هذا المنتدى