الوقت/التاريخ الآن هو الجمعة يوليو 01, 2022 1:09 am

2 نتيجة بحث عن index

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

أهلا بكم

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

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


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

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

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

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

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


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



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

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


الخطوة 1 :تعين الوسم index على المنتدى منتدى مصر التقني 103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8 والوسم index على المنتدى منتدى مصر التقني 4b0bfb3769bf24d80e15374dc37b0441e2616e33 هما متغيران يمثلان موضع اقل و اكبر عنصر بالمصفوفة  اضبط قيمة الوسم index على المنتدى منتدى مصر التقني 103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8 = الوسم index على المنتدى منتدى مصر التقني 2aae8864a3c1fec9585261791a809ddec1489950 وقيمة الوسم index على المنتدى منتدى مصر التقني 4b0bfb3769bf24d80e15374dc37b0441e2616e33الوسم index على المنتدى منتدى مصر التقني Fbd0b0f32b28f51962943ee9ede4fb34198a2521 بمعني حجم المصفوفة ناقص 1


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


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


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

  • إذا كانت القيمة المستهدفة  T أقل من قيمة الوسط mid اضبط قيمة الوسم index على المنتدى منتدى مصر التقني 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 =الوسم index على المنتدى منتدى مصر التقني Ed7e052f47e5069015943e2ad3c12363ac155250     

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

    الوسم index على المنتدى منتدى مصر التقني 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
  • الوسم index على المنتدى منتدى مصر التقني 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

    الوسم index على المنتدى منتدى مصر التقني 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
من طرف زهراء
في الجمعة يناير 22, 2021 9:42 am
 
ابحث في: الخوارميات Algorithms
موضوع: خوارزمية البحث الثنائي Binary Search Algorithm
المساهمات: 1
مشاهدة: 932

المصفوفات فى الجافا Java Arrays

أهلا بكم

من خلال هذا المقال سنتناول بالشرح مفهوم المصفوفات فى الجافا #Java Array، المقال سوف يغطي المواضيع التالية:



  1. ما هي المصفوفات  Arrays؟

  2. طرق إنشاء مصفوفة 

  3. الوصول إلى عنصر محدد في المصفوفات

  4. المصفوفات متعددة الأبعاد 

  5. تمرير بيانات مصفوفة إلى طريقة Method




ما هي المصفوفات  Arrays؟

المصفوفات في #Java هي هياكل بيانات متجانسة يتم تنفيذها في #Java ككائنات.حيث تقوم #Arrays بتخزين قيمة واحدة أو أكثر من نوع بيانات محدد بطريقة مفهرسة و يتم الوصول إلى عنصر محدد في المصفوفة بواسطة الفهرس الخاص به. 

طرق إنشاء المصفوفات :

الصيغة العامة للإعلان عن المصفوفة على النحو التالى :

المصفوفة ذات البعد الواحد....والصيغة العامة للإعلان عن المصفوفة ذات البعد الواحد كالتالي:

الوسم index على المنتدى منتدى مصر التقني 781125485


أو يمكن الإعلان عنها بنفس الصيغة السابقة مع وضع الأقواس بعد اسم المصفوفة كالتالي:

الوسم index على المنتدى منتدى مصر التقني 756900150


اذن لكي يتم إنشاء مصفوفة يجب عليك الاتى :


  • تحديد نوع البيانات المراد تخزينها فى المصفوفة data type
  • قوس مربع []
  • وضع اسم للمصفوفة 


مثال : انشاء مصفوفة باسم A تحتوي على بيانات من نوع int 

الكود:
int [] A;


أو يمكنك تبديل موضع [] مع اسم المصفوفة على النحو التالى :

الكود:
int A [] ;


بهذا كما موضح هو إعلاه قنما بإنشاء المصفوفة A ولكن لا يمكن تخزين بيانات بها بعد، بمعنى أنه تم إنشاء اسم متغير يشير إلى #null (لا شيء) في الذاكرة لذلك يجب علينا تهئية تلك المصفوفة وذلك بتحديد حجمها ويتم ذلك بعده طرق :

باستخدام الكلمة الاساسية #new ، وتعيينه إلى نوع بيانات المصفوفة على النحو التالى :

الكود:

int [] A;
A[] = new int[5];


أو يمكن تهئية المصفوفة و تحديد حجمها في سطر واحد كالتالي:

الوسم index على المنتدى منتدى مصر التقني 129786133

الوصول إلى عنصر محدد في المصفوفات :


وكما هو ظاهر اعلاه كل المصفوفات عناصرها مرقمة من 0 إلى (حجم المصفوفة -1) ويسمى هذا الترقيم بال #index فهو بمثابة عنوان للعنصر وبه نستطيع الوصول إليه.

مثلا المصفوفة A التى تم إنشائها وتحديد حجمها 5 لتخزين خمس أرقام فسيكون ال #index  لها من 0 إلى 4، إذ أن العنصر الأول سيكون متواجد عند ال#index رقم 0 والعنصر الثاني عند ال#index رقم 1، وهكذا إلى نهاية المصفوفة....فمثلا لو أردنا وضع القيمة 10 في المخزن الاول للمصفوفة سنقوم بكتابة الشفرة على النحو التالى :

الكود:
;A[0]=10


مثال اكثر توضيحا :

إنشاء مصفوفة باسم #month_days حجمها يتسع لعدد 12 مخزن ليتم تخزين عدد الايام لكل شهر ميلادى ..ثم طباعة عدد ايام شهر ابريل على النحو التالى :

الكود:
public static void main(String args[]) {
   int month_days[];
    month_days = new int[12];
    month_days[0] = 31;
    month_days[1] = 28;
    month_days[2] = 31;
    month_days[3] = 30;
    month_days[4] = 31;
    month_days[5] = 30;
    month_days[6] = 31;
    month_days[8] = 30;
    month_days[9] = 31;
    month_days[10] = 30;
    month_days[11] = 31;
     System.out.println("April has " + month_days[3] + " days.");
     }
}


المخرجات :

April has 30 days

و على الرغم من ذلك يمكنك يمكن تهيئة المصفوفة و تحديد حجمها عندما يتم الإعلان عنها مباشرة بتمرير القيم او العناصر المراد تخزينها بها في مُهيئ المصفوفة .حيث سيتم إنشاء المصفوفة تلقائيًا بشكل يكفي لاحتواء عدد العناصر التي تحددها في مُهيئ الصفيف. على النحو التالى :

الوسم index على المنتدى منتدى مصر التقني 151613972

مثال :
الكود:
class MyArray{
 
public static voide main(String args[]){
 
int month_days[ ] = {31,28,31,30,31,30,31,30,31,30,31};
 
System.out.println("April has " + month+days[3] + "days.");
 
}
 
}



المخرجات :

April has 30 days


 المصفوفة متعددة الأبعاد (ذات البعدين) Multidimensional array

ويمكن القول بأن المصفوفة ذات البعدين هي عبارة عن جدول يحتوي على صفوف وأعمدة .والصيغة العامة لهذه المصفوفة كالتالي :


الوسم index على المنتدى منتدى مصر التقني 145876847

ويتعب نفس طريقة انشاء و تهيئة المصفوفة أحادية البعد

الوسم index على المنتدى منتدى مصر التقني 422583293

تمرير مصفوفة إلى طريقة

يمكننا أيضًا تمرير المصفوفات إلى الطرق كما يمكننا تمرير قيم النوع البدائي إلى الأساليب...على النحو التالى :

الكود:
public class PMethods{
public static void display(int y[])
     {
             System.out.println(y[0]);
             System.out.println(y[1]);
             System.out.println(y[2]);
 
     }
public static void main(String args[])
     {
     int x[] = { 1, 2, 3 };
     display(x);
     }
}
من طرف زهراء
في الإثنين يناير 21, 2019 8:47 pm
 
ابحث في: أساسيات اللغة Java Basics
موضوع: المصفوفات فى الجافا Java Arrays
المساهمات: 0
مشاهدة: 993

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

انتقل الى: