Binary Search
تُعطى قائمة من الأعداد الصحيحة nums مرتبة ترتيبًا تصاعديًا، من دون تكرار أي قيمة، وعدد صحيح target. أَعِد فهرس target في nums، بدءًا من 0، أو -1 إذا لم يكن موجودًا في القائمة. استهدف زمنًا قدره O(log n)، ما يعني أنه لا يمكنك تفحّص كل عنصر.
الدالة
- numsinteger-array
- القائمة المرتبة من الأعداد الصحيحة المميزة
- targetinteger
- القيمة المراد البحث عنها
- تُرجعinteger
- فهرس target في nums، أو -1 إذا لم يكن موجودًا
القيود
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104numsمرتبة بترتيب تصاعدي صارم، لذا تظهر كل قيمة مرة واحدة.
أمثلة
- المدخلات
- nums = [-7, -2, 0, 4, 9, 15, 23]target = 9
- المخرجات
- 4
- الشرح
- قيمة
nums[4]هي 9. يبحث البرنامج عند الفهرس 3 (القيمة 4، وهي صغيرة جدًا)، ثم عند الفهرس 5 (القيمة 15، وهي كبيرة جدًا)، ثم عند الفهرس 4، حيث يجد 9.
- المدخلات
- nums = [1, 3, 5, 8, 13, 21]target = 10
- المخرجات
- -1
- الشرح
- سيكون 10 بين 8 و13، ولا يساوي أيٌّ منهما 10، لذا فهو غير موجود في القائمة. يتقلص نطاق البحث حتى يتجاوز
lohi، وتُرجع الدالة-1.
+15 اختبارات مخفية عند الإرسال
سؤال إضافي
إذا كان من الممكن أن تحتوي nums على قيم مكررة، فكيف ستُرجع الفهرس الأول لـ target، مع الحفاظ على O(log n)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
القائمة مرتبة. إذا قارنت
targetبأحد العناصر في المنتصف، فماذا يخبرك ذلك عن جميع العناصر على أحد جانبيه؟إذا كان
nums[mid] < target، فإنnums[mid]وكل ما يقع على يساره أصغر من اللازم، لذا لا يمكن أن يكونtargetإلا على اليمين. مقارنة واحدة تستبعد نصف العناصر المرشحة.احتفظ بفهرسين،
loوhi، حول الجزء من القائمة الذي قد يحتوي علىtarget. قارن بالعنصر الأوسط، وحرّكloأوhiمتجاوزًا إياه، وتوقّف عندما تجدtargetأو عندما يتجاوزlohi.
الحل
يؤدي فحص العناصر واحدًا تلو الآخر إلى العثور على target، لكنه يتجاهل الحقيقة الوحيدة التي تجعل المسألة مثيرة للاهتمام: القائمة مرتبة. تخبرك مقارنة واحدة مع العنصر الأوسط بأي نصف قد يظل يحتوي على target، لذا يمكنك استبعاد نصف العناصر المرشحة في كل خطوة. وهكذا، لا تحتاج قائمة تضم 10^4 عنصرًا إلى أكثر من 14 مقارنة، بدلًا من 10000.
امسح من اليسار إلى اليمين
الفكرة
تحقّق من كل فهرس بالترتيب، وأعِد أول فهرس تكون قيمته مساوية لـ target. إذا انتهت الحلقة دون العثور على تطابق، فهذا يعني أن target غير موجود في القائمة، لذا أَعِد -1. تتم مقارنة كل عنصر مرة واحدة، ما يجعل الإجابة صحيحة لأي قائمة، سواء أكانت مرتبة أم لا.
هذه العمومية هي موطن المشكلة. تتطلب قائمة تضم 10^4 عنصرًا ما يصل إلى 10000 مقارنة، ويزداد العمل بالتناسب مع n. لا يستفيد الفحص من حقيقة أن nums مرتبة، لذلك لا يحقق حد O(log n) الذي تتطلبه المهمة. يمكنك التوقف مبكرًا بمجرد أن تتجاوز إحدى القيم target، لكنك ستقرأ القائمة بأكملها في أسوأ الحالات.
الخوارزمية
- لكل فهرس
iمن 0 إلىn-1، قارنnums[i]معtarget. - إذا كانا متساويين، فأعِد
i. - بعد الحلقة، أعِد
-1.
def search(nums, target):
for i, value in enumerate(nums):
if value == target:
return i
return -1البحث الثنائي باستخدام فهرسين
الفكرة
احتفظ بمؤشرين، lo وhi، مع ضمان واحد: إذا كان target موجودًا في القائمة، فإن فهرسه يقع بين lo وhi، شاملًا كلا الطرفين. في البداية، يشمل هذا النطاق القائمة كلها، من 0 إلى n-1. انظر إلى الفهرس الأوسط mid. إذا كانت nums[mid] تساوي target، فقد انتهيت. إذا كانت أصغر، فبما أن القائمة مرتبة، فإن كل عنصر حتى mid أصغر أيضًا، لذا حرّك lo إلى mid + 1. وإذا كانت أكبر، فحرّك hi إلى mid - 1. يظل الضمان قائمًا بعد أيٍّ من الحركتين.
تتبّع المثال الأول، [-7, -2, 0, 4, 9, 15, 23] مع target = 9. النطاق من 0 إلى 6، وفهرسه الأوسط 3، وقيمته 4، وهي أصغر من المطلوب، لذا يصبح النطاق من 4 إلى 6. الفهرس الأوسط فيه هو 5، وقيمته 15، وهي أكبر من المطلوب، لذا يصبح النطاق من 4 إلى 4. في الفهرس 4 توجد القيمة 9: أعد 4.
إذا كان target غير موجود، يستمر النطاق في التقلّص حتى يتجاوز lo قيمة hi. عندئذٍ يصبح النطاق فارغًا، ويعني الضمان أن target غير موجود في أي موضع، وتُعيد -1. في كل خطوة ينخفض حجم النطاق إلى النصف، لذا تنفّذ الحلقة بحد أقصى نحو log2(n) + 1 مرة: 14 خطوة لقائمة تضم 10^4 عنصر. المؤشران هما كل الذاكرة الإضافية التي تحتاج إليها.
الخوارزمية
- عيّن
lo = 0وhi = n-1. - ما دام
lo ≤ hi، احسبmid = lo + (hi - lo) / 2. - إذا كانت
nums[mid]تساويtarget، فأعِدmid. - إذا كان
nums[mid] < target، فعيّنlo = mid + 1؛ وإلا فعيّنhi = mid - 1. - عندما تنتهي الحلقة، أعِد
-1.
def search(nums, target):
lo, hi = 0, len(nums) - 1 # target, if present, sits in nums[lo..hi]
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1 # nums[mid] and everything left of it is too small
else:
hi = mid - 1 # nums[mid] and everything right of it is too big
return -1
أخطاء شائعة وحالات حدّية
البحث الثنائي قصير، وتقريبًا كل الأخطاء فيه هي أخطاء بفارق واحد عند حدود النطاق.
- التكرار باستخدام
lo < hiبينما تبدأhiعند الفهرس الأخير. تتوقف الحلقة بينما لا يزال أحد الاحتمالات لم يُفحص، لذا فإنnums = [5]معtarget = 5تُرجع-1. مع نطاق شامل للطرفين، كرّر ما دامlo ≤ hi. - الانتقال إلى
lo = midأوhi = midمع نطاق شامل للطرفين. عندما يكونloوhiمتجاورين، تكونmidمساويةً لـloولا يتقلص النطاق أبدًا: حلقة لا نهائية. لقد تحققت بالفعل منnums[mid]، لذا تجاوزها بالانتقال إلىmid + 1أوmid - 1. - حساب
(lo + hi) / 2باستخدام عدد صحيح ذي عرض ثابت. يحدث تجاوز للسعة في المجموع عندما تتجاوز الفهارس نحو10^9. الحدود هنا أقل بكثير من ذلك، لكن استخدامlo + (hi - lo) / 2هو الأسلوب الآمن. - إرجاع
loعندما يكونtargetغير موجود. بعد انتهاء الحلقة، تكونloنقطة الإدراج، وهي فهرس صالح وليست-1. - نسيان الإزاحة في Lua وR. تبدأ القوائم فيهما من 1، لذا فإن الفهرس الذي تُرجعه هو الموضع ناقص 1.
أسئلة شائعة4
ما هو التعقيد الزمني للبحث الثنائي؟
O(log n). كل مقارنة تقسّم النطاق الذي قد يحتوي على الهدف إلى النصف، لذا بعد k خطوات، يتبقى على الأكثر n / 2^k من العناصر المرشحة. تحتاج قائمة تضم 10^4 عنصرًا إلى 14 مقارنة على الأكثر، وتحتاج قائمة تضم 10^9 عنصرًا إلى 30 مقارنة على الأكثر. يستخدم الإصدار التكراري مساحة إضافية O(1).
لماذا يتطلب البحث الثنائي مصفوفة مرتبة؟
تعتمد الخطوة التي تستبعد نصف القائمة على الترتيب. عندما يكون nums[mid] < target، يضمن الترتيب أن كل عنصر يقع يسار mid أصغر أيضًا من target، لذا لا يمكن لأي منها أن يطابق الهدف. أما في قائمة غير مرتبة، فلا تخبرك هذه المقارنة شيئًا عن العناصر الأخرى، وعليك التحقق منها جميعًا.
هل ينبغي أن يكون البحث الثنائي تكراريًا أم递يًا؟
كلاهما صحيح ويعملان في زمن O(log n). تستدعي النسخة العودية نفسها على أحد النصفين وتستخدم مساحة مكدس O(log n)؛ أما النسخة التكرارية فتحرّك lo وhi داخل حلقة وتستخدم O(1). يتوقع المحاورون عادةً استخدام الحلقة، وهي تتجنب أي حدّ للتكرار العودي.
كيف تتجنب تجاوز السعة عند حساب الفهرس الأوسط؟
اكتب mid = lo + (hi - lo) / 2 بدلًا من (lo + hi) / 2. يعطي الشكلان الفهرس نفسه، لكن الشكل الثاني يجمع فهرسين أولًا، وفي عدد صحيح ذي 32 بتًا يفيض هذا المجموع عندما تتجاوز الفهارس نحو 1.07 × 10^9. في Python وRuby، الأعداد الصحيحة غير محدودة، لذا يكون الشكل المختصر آمنًا هناك.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def search(nums, target):
# اكتب الكود هناالحالة 1
الحالة 2
المدخلات
nums = [-7, -2, 0, 4, 9, 15, 23] target = 9
المتوقع
4