خوارزمية البحث الثنائي هي خوارزمية تستخدم لإيجاد مدخلة في مصفوفة مرتبة تصاعديا أو تنازليا سواء كانت أرقام أو نصوص .ولان العناصر مرتبة فهنا يمكن الاستفادة من ذلك في تقسيم قائمة العناصر إلى نصفين فيتم تجاهل أحدهما واعتماد الأخرى في عملية البحث بناء على مقارنه هل العنصر الموجود في وسط القائمة أكبر من العنصر الذي نبحث عنه ام اصغر ام يساويه ؟ وتبدا عملية البحث من العنصر الذي يقع في وسط المصفوفة فاذا كان العنصر الذي نبحث عنه يساوي العنصر الذي في الوسط تنتهي عملية البحث اما إذا كانت القيمتان مختلفتان ستقوم الخوارزمية باجراء فحص جديد فاذا كان العنصر الذي نبحث عنه أكبر من العنصر الذي في الوسط سيتم البحث في الجزء الأيمن من المصفوفة ويستثنى من البحث الجزء الأيسر اما إذا كان العنصر الذي نبحث عنه اصغر سيتم البحث في الجزء الأيسر من المصفوفة ويستثنى من البحث الجزء الأيمن.في كل مرحلة، تقارن الخوارزمية بين قيمة العنصر المدخل (المراد البحث عنه في المصفوفة) مع قيمة العنصر الأوسط في المصفوفة.[1][2][3] إذا كانت القيمتان متساويتين، إذن تم العثور على على عنصر مطابق، ويتم ارجاع مؤشر له، أو موقعه في المصفوفة. واذا لما تكن القيمتان متساويتين، إذا كانت قيمة العنصر المدخل اصغر من قيمة العنصر الأوسط، تكرر الخوارزمة هذه العملية على المصفوفة الفرعية على يسار العنصر الأوسط، أو إذا كانت قيمة العنصر المدخل أكبر، على المصفوفة الفرعية على اليمين. إذا تم تقليص المصفوفة لتصبح فارغة، لم يتم العثور على عنصر مطابق، ويتم ارجاع قيمة استثنائية "غير موجود".وسيتم تقسيم الجزء الأيمن أو الأيسر إلى نصفين ويتم تكرار عملية البحث حتى الحصول على مصفوفة تتكون من خانة واحدة قيمتها مساوية للعنصر الذي نبحث عنه أو مختلفة عنه وهنا نكون وصلنا إلى النتيجة النهائية والتي تتمثل في تحديد مكان العنصر الذي نبحث عنه عن طريق تحديد رقم الفهرس وهو مكان العنصر . ايجابيات هذه الخوارزمية اننا نقلص عدد عناصر المصفوفة في كل تكرار إلى النصف . سلبياتها انها أكثر تعقيدا من خوارزمية البحث الخطي وتشترط ان تكون العناصر مرتبة عند البحث.
البحث الثنائي ينّصف (يقلص للنصف) عدد العناصر المرجو فحصها في كل تكرار، ولذلك تحديد موقع عنصر (أو تحديد غيابه) ياخد زمنا لوغاريتميا. البحث الثنائي هو خوارزمية بحث من نوع فرق تسد.
مثال:
109876543210 98817268554122191350
وهنا سوف نقوم بالبحث أيضا عن العدد 55 ولكن بطريقة البحث الثنائي Middle=first+last/2 هنا المتوسط يساوي 0+10\2=5 في هذه الحالة سوف نقوم باستثناء الجهة اليسرى من البحث لان العدد الذي نبحث عنه أكبر من المتوسط أصبحت المصفوفة التي نبحث فيها 109876 988172 68 55
سوف نقوم بإخراج المتوسط مرة أخرى ولكن في هذه الحالة تغير العنصر الأول الذي سوف نبدا به اما العنصر الاخير فبقي ثابتا ناخذ المتوسط في الحالة الأولي +1 لمعرفة قيمة العنصر الأول First=middle+1 First=5+1=6 Middle=first+last/2
ناخذ العدد الأقل دون كسورMiddle=6+11/2=8
سوف نقوم بتقسيم المصفوفة بناء على المتوسط الجديد وسوف تصبح المصفوفة بالشكل التالي
76 6855
هنا استثنينا من البحث الجهة اليمنى لذلك سوف يتغير حساب المتوسط للعنصر الاخير فتصبح معادلة العنصر الاخير هي 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.length – 1; 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; } // غير موجود return –1; }
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).
مراجع
- A000225. Retrieved 7 May 2016. نسخة محفوظة 09 نوفمبر 2017 على موقع واي باك مشين.
- "List<T>.BinarySearch Method (T)". Microsoft Developer Network. مؤرشف من الأصل في 15 أغسطس 201810 أبريل 2016.
- Flores, Ivan; Madpis, George (1971). "Average binary search length for dense ordered lists". Communications of the ACM. 14 (9): 602–603. doi:10.1145/362663.362752.