Find First and Last Position of Element in Sorted Array
تُعطى قائمة من الأعداد الصحيحة nums مرتبة ترتيبًا غير تنازلي، لذا قد تتكرر قيمة ما، وعدد صحيح target. أعد قائمة من فهرسين، يبدأ العد فيهما من 0: الموضع الأول والموضع الأخير اللذان يظهر فيهما target. إذا لم يكن target موجودًا في القائمة، فأعد [-1, -1]. اسعَ إلى تحقيق زمن تنفيذ O(log n).
الدالة
- numsinteger-array
- قائمة الأعداد الصحيحة المرتبة، والتي قد تتكرر فيها القيم
- targetinteger
- القيمة المطلوب البحث عنها
- تُرجعinteger-array
- الفهرس الأول والفهرس الأخير لـ target، أو [-1, -1] إذا كان غير موجود
القيود
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104numsمرتبة بترتيب غير تنازلي.
أمثلة
- المدخلات
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 5
- المخرجات
- [1, 3]
- الشرح
- توجد النسخ الثلاث من 5 عند الفهارس 1 و2 و3، لذا يبدأ التتابع عند الفهرس 1 وينتهي عند الفهرس 3. يحتوي الفهرس 0 على 3 ويحتوي الفهرس 4 على 8، لذا لا يمكن أن يمتد التتابع إلى أبعد من ذلك.
- المدخلات
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 7
- المخرجات
- [-1, -1]
- الشرح
- سيكون 7 بين 5 عند الفهرس 3 و8 عند الفهرس 4، ولا يساوي أيٌّ منهما 7. لا تحتوي القائمة على نسخة منه، لذا تكون الإجابة
[-1, -1].
سؤال إضافي
إذا كانت القائمة نفسها تتلقى آلاف الاستعلامات عن أهداف مختلفة، فهل يمكن لتمرير واحد عليها مسبقًا أن يجعل كل استعلام أسرع من O(log n)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
بما أن
numsمرتبة، فإن جميع نسخtargetمتجاورة في سلسلة واحدة. تحتاج إلى طرفي هذه السلسلة.قد يستغرق العثور على نسخة واحدة والتحرك للخارج
O(n)عندما يكون التسلسل طويلًا. بدلًا من ذلك، غيّر البحث الثنائي بحيث يواصل البحث إلى اليسار بعد العثور على تطابق: عندها يتوقف عند أول فهرس تكون قيمته أكبر من أو تساوي العدد الذي تبحث عنه.اكتب دالة مساعدة تُرجع أول فهرس يحقق
nums[i] ≥ value. استدعها باستخدامtargetللحصول على بداية التتابع، وتحقق من أن القيمة هناك هيtarget، ثم استدعها باستخدامtarget + 1: ينتهي التتابع عند الفهرس الذي يسبق ذلك بواحد.
الحل
يتوقف البحث الثنائي العادي عند أي نسخة من target يصادفها، ويمكن أن تكون هذه النسخة في أي موضع ضمن التتابع. ابحث عن الحد الأدنى بدلًا من ذلك: أول فهرس تكون قيمته أكبر من أو تساوي عددًا معيّنًا. يعطي الحدان الأدنى لكل من target وtarget + 1 طرفَي التتابع في O(log n).
افحص القائمة بأكملها
الفكرة
امشِ على القائمة مرة واحدة. أول فهرس يحتوي على target هو البداية، وآخر فهرس هو النهاية. إذا لم يظهر target مطلقًا، فسيبقى كلاهما -1.
تنجح هذه الطريقة مع أي قائمة، مرتبة كانت أم لا، وهذه هي نقطة ضعفها: فهي تقرأ جميع القيم البالغ عددها n. تتطلب قائمة تحتوي على 10^4 قيمة 10,000 مقارنة، بينما يكفي نحو 28 مقارنة.
الخوارزمية
- عيّن
first = last = -1. - لكل فهرس
i، إذا كانتnums[i]تساويtarget، فعيّنfirst = iعندما تكونfirstلا تزال-1، وعيّنlast = i. - أعِد
[first, last].
def searchRange(nums, target):
first = last = -1
for i, value in enumerate(nums):
if value == target:
if first == -1:
first = i # the first match fixes the start
last = i # every later match moves the end
return [first, last]اعثر على نسخة واحدة، ثم وسّعها
الفكرة
ابحث بالبحث الثنائي عن أي فهرس يحتوي على target. القائمة مرتبة، لذا تقع كل النسخ في مقطع متصل حول ذلك الفهرس: تحرّك يسارًا ويمينًا ما دام العنصر المجاور لا يزال target.
تستغرق عملية البحث O(log n)، ويستغرق المرور خطوة واحدة لكل نسخة، أي k خطوة إجمالًا. عندما يكون معظم عناصر القائمة هو target، لنقل 10^4 نسخة، يقرأ المرور كل قيمة، وتعود بذلك إلى المسح الخطي.
الخوارزمية
- ابحث بحثًا ثنائيًا عن أي فهرس
foundبحيثnums[found] == target. - إذا لم يوجد، فأعِد
[-1, -1]. - حرّك
firstإلى اليسار انطلاقًا منfoundما دامت القيمة التي تسبقه تساويtarget. - حرّك
lastإلى اليمين انطلاقًا منfoundما دامت القيمة التي تليه تساويtarget. - أعِد
[first, last].
def searchRange(nums, target):
# An ordinary binary search finds some copy of target, if there is one.
lo, hi = 0, len(nums) - 1
found = -1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
found = mid
break
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
if found == -1:
return [-1, -1]
# The copies sit next to each other, so walk out to both ends of the run.
first = last = found
while first > 0 and nums[first - 1] == target:
first -= 1
while last < len(nums) - 1 and nums[last + 1] == target:
last += 1
return [first, last]بحثان ثنائيان عن الحد الأدنى
الفكرة
اطرح سؤالًا مختلفًا: ما أول فهرس تكون قيمته على الأقل value؟ هذا الفهرس هو الحد السفلي، أو n إذا لم تستوفِ أي قيمة الشرط. احتفظ بنطاق نصف مفتوح [lo, hi) يحتويه دائمًا. إذا كان nums[mid] < value، فإن mid وكل ما قبله أصغر من المطلوب. وإلا، فإن mid يستوفي الشرط، لكن قد يستوفيه فهرس أسبق أيضًا، لذا يبقى mid ضمن النطاق ويصبح hi الجديد. لا تتوقف الحلقة مبكرًا عند العثور على تطابق.
الحد السفلي لـ target هو الموضع الذي يبدأ عنده تتابع قيمه. القيم أعداد صحيحة، لذا تقع أول قيمة أكبر من target عند الحد السفلي لـ target + 1، وينتهي التتابع عند الفهرس السابق له. في المثال الأول، الحد السفلي لـ 5 هو 1 والحد السفلي لـ 6 هو 4، حيث تقع 8: لذا يكون التتابع [1, 3]. يستغرق البحثان نحو 28 خطوة لقيم 10^4، مهما كان طول التتابع.
الخوارزمية
- اكتب
lowerBound(value): ابدأ بـlo = 0وhi = n؛ ما دامlo < hi، إذا كانnums[mid] < valueفاجعلlo = mid + 1، وإلا فاجعلhi = mid؛ أعدlo. - اجعل
first = lowerBound(target). - إذا كان
first == nأوnums[first] != target، فأعد[-1, -1]. - اجعل
last = lowerBound(target + 1) - 1وأعد[first, last].
def lowerBound(nums, value):
# The first index whose number is at least value, or len(nums) if none is.
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < value:
lo = mid + 1 # nums[mid] and everything before it is too small
else:
hi = mid # nums[mid] qualifies, but an earlier index might too
return lo
def searchRange(nums, target):
first = lowerBound(nums, target)
if first == len(nums) or nums[first] != target:
return [-1, -1]
# The run of target ends right before the first number above target.
last = lowerBound(nums, target + 1) - 1
return [first, last]
أخطاء شائعة وحالات حدّية
- إرجاع النتيجة فورًا عند
nums[mid] == target. قد يكون هذا الفهرس في أي موضع ضمن التتابع: في[3, 5, 5, 5, 8]يكون العنصر الأوسط الأول عند الفهرس 2، وهو ليس أيًّا من الطرفين. - كتابة
hi = mid - 1في البحث عن الحد الأدنى عندماnums[mid] ≥ value. هذا يستبعدmid، مع أنه قد يكون الإجابة. - قراءة
nums[first]دون التحقق منfirst < n. عندما يكونtargetأكبر من كل القيم، كما ستكون 13 في الأمثلة، يكون الحد الأدنى هوn، أي موضعًا واحدًا بعد النهاية. - نسيان الإزاحة في Lua وR. تبدأ قوائمهما من 1، لذا اطرح 1 من كلا الموضعين.
أسئلة شائعة3
ما التعقيد الزمني لإيجاد الموضعين الأول والأخير؟
زمن O(log n) ومساحة O(1)، باستخدام بحثين ثنائيين. لا يتوقف أيٌّ منهما عند العثور على تطابق، لذا لا تعتمد الكلفة على عدد نسخ القيمة المستهدفة: نحو 14 خطوة لكل بحث من أجل 10^4 قيمة.
ما الحد الأدنى في البحث الثنائي؟
الحد الأدنى لقيمة ما هو أول فهرس يكون العنصر عنده أكبر من تلك القيمة أو مساويًا لها، أو طول القائمة إذا لم يوجد مثل هذا العنصر. وهو الموضع الذي ستُدرج فيه القيمة للحفاظ على ترتيب القائمة. أما الحد الأعلى فهو أول فهرس يكون العنصر عنده أكبر من تلك القيمة تمامًا.
هل يمكن لدالة واحدة للبحث الثنائي أن تعثر على كلٍّ من الفهرس الأول والأخير؟
نعم. أضف إلى البحث علامةً: عند العثور على تطابق، سجّل الفهرس وواصل البحث إلى اليسار للعثور على أول نسخة، أو إلى اليمين للعثور على الأخيرة. وينجح أيضًا إجراء بحث عن الحد الأدنى على target وعلى target + 1. كلاهما يعمل بزمن O(log n).
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def searchRange(nums, target):
# اكتب الكود هنااختبار #1
اختبار #2
الوسائط
nums = [3, 5, 5, 5, 8, 9, 9, 12] target = 5
الإخراج المتوقع
[1, 3]