كيف يعمل البحث الثنائي، وما الذي يتطلبه؟

Question

Accepted Answer

**البحث الثنائي** يجد هدفاً في مصفوفة **مرتبة** بتقسيم نطاق البحث بشكل متكرر. كل مقارنة تستبعد نصف العناصر المتبقية، مما يعطي وقت **O(log n)**. ## الفكرة الأساسية انظر إلى العنصر الأوسط. إذا كان مساوياً للهدف، فقد انتهينا. إذا كان الهدف أصغر، ابحث عن النصف الأيسر؛ إذا كان أكبر، ابحث عن النصف الأيمن. كرر حتى تجد القيمة أو يصبح النطاق فارغاً. ## مثال ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 # middle index if arr[mid] == target: return mid # found it elif arr[mid] < target: lo = mid + 1 # discard left half else: hi = mid - 1 # discard right half return -1 # not present binary_search([1, 3, 5, 7, 9], 7) # -> 3 ``` ## تتبع التنفيذ ```text Search 7 in [1,3,5,7,9] lo=0 hi=4 mid=2 -> 5 < 7 => lo=3 lo=3 hi=4 mid=3 -> 7 == 7 => return 3 ``` ## التعقيد الزمني والمكاني - **الوقت:** O(log n). **المساحة:** O(1) بالتنفيذ التكراري. ## المزالق الشائعة **يجب أن تكون المدخلات مرتبة** — وإلا فإن النتائج ستكون بلا معنى. احذر من أخطاء off-by-one في `lo`/`hi` وتجاوز الأعداد الصحيحة في بعض لغات البرمجة (استخدم `lo + (hi-lo)//2`). ## لماذا هذا مهم تقسيم مساحة البحث بالنصف يحول البحث في مليون عنصر إلى حوالي 20 مقارنة فقط. نمط فرّق تسد الكامن وراءه يظهر مجدداً في الأشجار وقواعد البيانات وعدد لا يحصى من مسائل المقابلات. معرفة متطلبها الأساسي الوحيد — المدخلات المرتبة — تحميك من خطأ دقيق وكلاسيكي.