تكرار السؤال: …
الإجابة المختصرة
تعمل على مصفوفة مرتبة مسبقاً بتقسيم نطاق البحث إلى النصف في كل خطوة بزمن O(log N)، ولتفادي طفحان الأعداد الصحيحة يُحسب المنتصف عبر low + (high - low) / 2 بدلاً من (low + high) / 2.
الشرح
إذا كانت قيمتا low و high قريبتين من الحد الأقصى للأعداد الصحيحة (مثل 2^31 - 1)، فإن جمعهما (low + high) يسبب طفحاناً عددياً (Integer Overflow) يتحول إلى رقم سالب في لغات مثل Java و C++، مما يؤدي لرمي ArrayIndexOutOfBoundsException. يمكن أيضاً تطبيق البحث الثنائي ليس فقط على مصفوفات الأرقام، بل على فضاءات الإجابات المستمرة (Binary Search on Answer Space) لحل مسائل التحسين والحد الأدنى للحد الأقصى.
مثال بالكود
function binarySearch(arr: number[], target: number): number {
let low = 0, high = arr.length - 1;
while (low <= high) {
const mid = low + Math.floor((high - low) / 2); // آمن من الـ Overflow
if (arr[mid] === target) return mid;
if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}أخطاء شائعة
- تطبيق البحث الثنائي على مصفوفة غير مرتبة وتوقع نتائج صحيحة.