خوارزمية بحث ثنائي

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

خوارزمية البحث الثنائي هي خوارزمية تستخدم لإيجاد مدخلة في مصفوفة مرتبة تصاعديا او تنازليا سواء كانت ارقام او نصوص .ولان العناصر مرتبة فهنا يمكن الاستفادة من ذلك في تقسيم قائمة العناصر إلى نصفين فيتم تجاهل احدهما واعتماد الاخرى في عملية البحث بناء على مقارنه هل العنصر الموجود في وسط القائمة اكبر من العنصر الذي نبحث عنه ام اصغر ام يساويه ؟ وتبدا عملية البحث من العنصر الذي يقع في وسط المصفوفة فاذا كان العنصر الذي نبحث عنه يساوي العنصر الذي في الوسط تنتهي عملية البحث اما اذا كانت القيمتان مختلفتان ستقوم الخوارزمية باجراء فحص جديد فاذا كان العنصر الذي نبحث عنه اكبر من العنصر الذي في الوسط سيتم البحث في الجزء الايمن من المصفوفة ويستثنى من البحث الجزء الايسر اما اذا كان العنصر الذي نبحث عنه اصغر سيتم البحث في الجزء الايسر من المصفوفة ويستثنى من البحث الجزء الايمن.في كل مرحلة, تقارن الخوارزمية بين قيمة العنصر المدخل (المراد البحث عنه في المصفوفة) مع قيمة العنصر الأوسط في المصفوفة. إذا كانت القيمتان متساويتين, إذن تم العثور على على عنصر مطابق, ويتم ارجاع مؤشر له, أو موقعه في المصفوفة. واذا لما تكن القيمتان متساويتين, إذا كانت قيمة العنصر المدخل اصغر من قيمة العنصر الأوسط, تكرر الخوارزمة هذه العملية على المصفوفة الفرعية على يسار العنصر الأوسط, أو إذا كانت قيمة العنصر المدخل أكبر, على المصفوفة الفرعية على اليمين. إذا تم تقليص المصفوفة لتصبح فارغة, لم يتم العثور على عنصر مطابق, ويتم ارجاع قيمة استثنائية "غير موجود".وسيتم تقسيم الجزء الايمن او الايسر إلى نصفين ويتم تكرار عملية البحث حتى الحصول على مصفوفة تتكون من خانة واحدة قيمتها مساوية للعنصر الذي نبحث عنه او مختلفة عنه وهنا نكون وصلنا إلى النتيجة النهائية والتي تتمثل في تحديد مكان العنصر الذي نبحث عنه عن طريق تحديد رقم الفهرس وهو مكان العنصر . ايجابيات هذه الخوارزمية اننا نقلص عدد عناصر المصفوفة في كل تكرار إلى النصف . سلبياتها انها اكثر تعقيدا من خوارزمية البحث الخطي وتشترط ان تكون العناصر مرتبة عند البحث.


البحث الثنائي ينّصف (يقلص للنصف) عدد العناصر المرجو فحصها في كل تكرار, ولذلك تحديد موقع عنصر (أو تحديد غيابه) ياخد زمنا لوغاريتميا. البحث الثنائي هو خوارزمية بحث من نوع فرق تسد.


مثال:

10 9 8 7 6 5 4 3 2 1 0 98 81 72 68 55 41 22 19 13 5 0

وهنا سوف نقوم بالبحث أيضا عن العدد 55 ولكن بطريقة البحث الثنائي Middle=first+last/2 هنا المتوسط يساوي 0+10\2=5 في هذه الحالة سوف نقوم باستثناء الجهة اليسرى من البحث لان العدد الذي نبحث عنه اكبر من المتوسط اصبحت المصفوفة التي نبحث فيها 10 9 8 7 6 98 81 72 68 55


سوف نقوم باخراج المتوسط مرة اخرى ولكن في هذه الحالة تغير العنصر الاول الذي سوف نبدا به اما العنصر الاخير فبقي ثابتا ناخذ المتوسط في الحالة الاولي +1 لمعرفة قيمة العنصر الاول First=middle+1 First=5+1=6 Middle=first+last/2

ناخذ العدد الاقل دون كسورMiddle=6+11/2=8

سوف نقوم بتقسيم المصفوفة بناء على المتوسط الجديد وسوف تصبح المصفوفة بالشكل التالي

7 6 68 55

هنا استثنينا من البحث الجهة اليمنى لذلك سوف يتغير حساب المتوسط للعنصر الاخير فتصبح معادلة العنصر الاخير هي Last=middle-1 Last=8-1=7 Middle=first+last/2 Middle=6+7/2 Middle=13/2=6 وهنا انتهت عملية البحث لاننا وجدنا العنصر الذي نبحث عنه الخوارزمية التي تعبر عن ذلك هي : Int first=0; Int size; Int last=size -1; Int middle; Boolean found=false; While(first<=last&&!found){ Middle=(first+last)/2; If (item==A[middle]) Found=true; Else if(item<A[middle]) Last=middle-1; Else First=middle+1;


طرق التحقيق[عدل]

1. تكراري (Iterative)[عدل]

تطبيق تكراري بلغة الجافا:

public static int binarySearch(int[] arr, int value) {
   int low = 0, mid, high = arr.length1;
   while (low <= high) {
     mid = (low + high) / 2;
     if (value < arr[mid])  
       high = mid – 1;
     else if (value > arr[mid])
       low = mid + 1;
     else
       return mid;
   } 
 
// غير موجود
   return1;
}

2. عودي (Recursive)[عدل]

تطبيق آخر بسيط هو تطبيق عودي

public static int binarySearch(int[] arr, int value, int low, int high) {
       if (high < low)
           return -1; // غير موجود
       mid = (low + high) / 2;
       if (arr[mid] > value)
           return binarySearch(arr, value, low, mid-1);
       else if (arr[mid] < value)
           return binarySearch(arr, value, mid+1, high);
       else
           return mid; // موجود
}

حيث يتم استداعائه بقيم أولية لـ low وhigh مع 0 وN-1 (طول المصفوفة -1).

انظر أيضا[عدل]