الـ Integer Overflow: ليه (low + high) / 2 باج في كل بحث ثنائي تقريبًا
هذا المقال يتطلب مستوى: محترف. لو انت مبتدئ أو متوسط، هيفيدك، لكنه بيفترض إنك تعرف البحث الثنائي (binary search) وتقرأ كود Java.
سطر واحد بتكتبه في أي بحث ثنائي بيحسب نقطة المنتصف: mid = (low + high) / 2. السطر ده صحيح رياضيًا وغلط برمجيًا، وظل باجًا نائمًا في مكتبة Java القياسية تسع سنوات. بعد ما تخلص، هتعرف تكتشف نفس الخطأ في أي كود عندك وتصلّحه في ثانية.
المشكلة باختصار
البحث الثنائي بيقسم المصفوفة نص كل خطوة. عشان يعمل كده لازم يحسب المؤشر في النص: mid. الطريقة البديهية بتجمع low + high الأول. المشكلة إن الناتج ممكن يتعدّى أقصى قيمة يشيلها العدد الصحيح، فيلتف (wraps) لرقم سالب. المؤشر السالب بيكسر الوصول للمصفوفة أو بيرجّع نتيجة غلط. الخطأ مبيظهرش على المصفوفات الصغيرة، فبيعدّي كل الاختبارات ويوصل للـ production.
ليه العدد بيلتف؟ ابدأ بالعدّاد
تخيّل عدّاد مسافة عربية بستة أرقام. أقصى رقم يوصّله 999999. لو مشيت كيلومتر واحد زيادة، مش هيبقى 1000000، هيرجع لـ 000000 لأنه مفيش خانة سابعة. ده بالظبط اللي بيحصل للعدد الصحيح في الذاكرة: عدد الخانات ثابت، ولما تتخطّى السقف بترجع من الأول.
علميًا: الـ int في Java وC وGo بيتخزّن في 32 بت بنظام المتممة الثنائية (two's complement). أقصى قيمة موجبة هي 2,147,483,647 (أي 2^31 − 1). البت الأعلى محجوز للإشارة. أول ما المجموع يعدّي القيمة دي، البت الأعلى بيتقلب، فالعدد بيتفسّر كرقم سالب. مفيش استثناء بيترمى، مفيش تحذير: العملية بتكمّل بصمت بقيمة غلط. ده الفرق الخطير: الـ overflow في الأعداد الصحيحة مش error، ده سلوك معرّف بيديك رقم خاطئ.
الخطأ في البحث الثنائي بالتفصيل
خُد مصفوفة كبيرة، وافترض إن البحث وصل لحالة low = 1,500,000,000 و high = 2,000,000,000. دي أرقام واقعية لو عندك مصفوفة فيها أكثر من مليار عنصر.
المجموع low + high = 3,500,000,000. الرقم ده أكبر من سقف الـ int (2,147,483,647)، فبيلتف إلى -794,967,296. وبقسمته على 2 بيطلع mid = -397,483,648، وهو مؤشر سالب. النتيجة: ArrayIndexOutOfBoundsException في Java، أو قراءة ذاكرة خارج الحدود في C.
كود يفجّر الخطأ ويصلّحه
جرّب الكود ده بنفسك. لاحظ إني استخدمت Java قصدًا: في Python الأعداد الصحيحة عندها دقة لا نهائية فالـ overflow ده مبيحصلش أصلًا، وده بالظبط سبب أهمية معرفة لغتك.
public class BinarySearchBug {
public static void main(String[] args) {
int low = 1_500_000_000;
int high = 2_000_000_000;
// الطريقة الشائعة — بها الخطأ
int buggyMid = (low + high) / 2;
System.out.println("buggyMid = " + buggyMid); // -397483648 (مؤشر سالب!)
// الإصلاح — لا يتجاوز السقف أبدًا
int safeMid = low + (high - low) / 2;
System.out.println("safeMid = " + safeMid); // 1750000000 (صحيح)
}
}