Search in Rotated Sorted Array
تم ترتيب قائمة من الأعداد الصحيحة المتميزة بترتيب تصاعدي، ثم دُوّرت: نُقل عدد من العناصر، قد يكون صفرًا، من المقدمة إلى النهاية بالترتيب نفسه. على سبيل المثال، تدوير [2, 5, 8, 11, 15, 19, 23] بمقدار 4 ينتج عنه [15, 19, 23, 2, 5, 8, 11]. تُعطى القائمة المدورة nums والعدد الصحيح target. أعد فهرس target في nums، بدءًا من 0، أو -1 إذا لم يكن موجودًا، بزمن O(log n).
الدالة
- numsinteger-array
- القائمة المُدوَّرة المرتبة من أعداد صحيحة متميزة
- targetinteger
- القيمة التي يجب البحث عنها
- تُرجعinteger
- فهرس target في nums، أو -1 إذا لم يكن موجودًا
القيود
1 ≤ nums.length ≤ 5000-104 ≤ nums[i], target ≤ 104- جميع القيم في
numsمختلفة. numsقائمة متزايدة دُوِّرت بمقدار ماkبحيث0 ≤ k < nums.length؛ وإذا كانk = 0فإنها تظل دون تدوير.
أمثلة
- المدخلات
- nums = [15, 19, 23, 2, 5, 8, 11]target = 5
- المخرجات
- 4
- الشرح
- يقع 5 عند الفهرس 4. ويحمل العنصر الأوسط الأول، عند الفهرس 3، القيمة 2، لذا فإن النصف الأيمن
[2, 5, 8, 11]هو المرتب، وتقع 5 بين 2 و11. ويحمل العنصر الأوسط التالي، عند الفهرس 5، القيمة 8؛ ويحتوي الجزء الأيسر المرتب[5, 8]على 5، مما يؤدي إلى الفهرس 4.
- المدخلات
- nums = [40, 50, 60, 70, 10, 20, 30]target = 65
- المخرجات
- -1
- الشرح
- ينبغي أن يكون 65 بين 60 و70، ولا يوجد أي عنصر يحتوي عليه. يقع العنصر الأوسط الأول، 70 عند الفهرس 3، بحيث يكون 65 ضمن الجزء الأيسر المرتب
[40, 50, 60, 70]. يضيق النطاق داخل هذا الجزء حتى يصبح فارغًا، لذا تُرجع الدالة-1.
- المدخلات
- nums = [8, 13, 21, 1, 3, 5]target = 13
- المخرجات
- 1
- الشرح
- العنصر الأوسط الأول، عند الفهرس 2، يحتوي على 21. الجزء الأيسر
[8, 13, 21]مرتب، و13 يقع بين 8 و21، لذا يُستبعد الجزء الأيمن بالكامل. ثم يعثر البحث على 13 عند الفهرس 1.
+23 اختبارات مخفية عند الإرسال
سؤال إضافي
إذا كان من الممكن أن تحتوي nums على قيم مكررة، فلا يمكن لأي خوارزمية أن تضمن O(log n). هل يمكنك إثبات ذلك؟ أنشئ قائمة مُدارة من القيم 1، تتضمن قيمة 0 واحدة مخفية، بحيث يتعين على أي عملية بحث عن 0 قراءة كل عنصر.
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
اختر أي فهرس في المنتصف وانظر إلى النصفين على جانبيه. أنشأ التدوير موضعًا واحدًا تنخفض فيه القيم، من الأكبر إلى الأصغر. هل يمكن أن يحتوي كلا النصفين على هذا الانخفاض؟
يكون نصف واحد على الأقل مرتبًا دائمًا، وتخبرك مقارنة
nums[lo]معnums[mid]أي النصفين هو المرتب. بالنسبة إلى النصف المرتب، يمكنك التحقق بخطوة واحدة مما إذا كانتtargetتقع بين قيمته الأولى والأخيرة.أبقِ
loوhiحول الجزء الذي قد يظل يحتوي علىtarget. في كل خطوة، إذا كان نطاق القيم في النصف المرتب يحتوي علىtarget، فأبقِ ذلك النصف؛ وإلا فأبقِ النصف الآخر. توقّف عندما تعثر علىtargetأو يصبح النطاق فارغًا.
الحل
القائمة المرتبة بعد تدويرها تتكوّن من مقطعين مرتبين موضوعين أحدهما بعد الآخر: [15, 19, 23] ثم [2, 5, 8, 11]. يفشل البحث الثنائي العادي معها، لأن مقارنة target بالقيمة الوسطى لم تعد تخبرك أي الجانبين يحتوي على target. يعتمد الحل على حقيقة واحدة: أينما قسمت القائمة، يكون نصف واحد على الأقل مرتبًا بالكامل، وبالنسبة إلى النصف المرتب يمكنك أن تعرف بمقارنة واحدة ما إذا كان target يمكن أن يكون بداخله.
افحص كل عنصر
الفكرة
افحص كل فهرس بالترتيب وأعِد أول فهرس تكون قيمته مساوية لـ target. إذا انتهت الحلقة دون العثور على تطابق، فأعِد -1. القيم متميزة، لذا فإن أول تطابق هو الوحيد، ويكون البحث صحيحًا لأي قائمة، سواء أكانت مدوّرة أم لا.
إنه يتجاهل كل ما تخبرك به المسألة. تتكوّن القائمة من مقطعين مرتّبين، ومع ذلك يفحص البحث ما يصل إلى 5000 عنصر، بينما يحتاج البحث الثنائي إلى نحو 13 مقارنة. وتزداد الفجوة مع حجم المدخلات: فمليون عنصر يتطلب مليون مقارنة، مقابل نحو 20 مقارنة. تطلب المسألة O(log n)، لذا فهذا هو الحل الأساسي الذي ينبغي تحسينه، وليس الإجابة.
الخوارزمية
- لكل فهرس
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اعثر على نقطة الدوران، ثم ابحث بحثًا ثنائيًا
الفكرة
القائمة المدورة تتكون من مقطعين مرتبين، ويبدأ المقطع الثاني بأصغر قيمة. لنسمِّ فهرسه k. بعد معرفة k، تتحول المسألة إلى بحث ثنائي عادي: nums[k..n-1] مرتب ويحتوي على القيم من nums[k] إلى nums[n-1]، وnums[0..k-1] مرتب ويحتوي على كل القيم الأكبر. تحدد مقارنة واحدة بين target وnums[k] وnums[n-1] المقطع الذي سنبحث فيه.
للعثور على k، أجرِ بحثًا ثنائيًا عن موضع الهبوط. قارن القيمة الوسطى بآخر قيمة في النطاق، nums[hi]. إذا كان nums[mid] > nums[hi]، فهذا يعني أن القيم تهبط في موضع ما بعد mid، لذا تقع أصغر قيمة إلى يمينه: عيّن lo = mid + 1. وإلا فإن nums[mid..hi] يتزايد دون هبوط، لذا تقع أصغر قيمة عند mid أو قبله: عيّن hi = mid، مع إبقاء mid ضمن النطاق. عندما يلتقي lo وhi، يكون هذا الفهرس هو k.
تتبّع المثال الأول، [15, 19, 23, 2, 5, 8, 11] مع target = 5. القيمة الوسطى 2 ليست أكبر من 11، لذا تصبح hi مساويةً لـ3؛ ثم تكون 19 أكبر من 2، لذا تصبح lo مساويةً لـ2؛ ثم تكون 23 أكبر من 2، لذا تصبح lo مساويةً لـ3، ويكون k = 3. بما أن 5 تقع بين nums[3] = 2 وnums[6] = 11، فابحث في الفهارس من 3 إلى 6، حيث يعثر البحث الثنائي على 5 عند الفهرس 4. يستغرق البحثان الثنائيان نحو 2 log2 n خطوة.
الخوارزمية
- عيّن
lo = 0وhi = n-1. ما دامlo < hi، احسبmid؛ إذا كانnums[mid] > nums[hi]فعيّنlo = mid + 1، وإلا فعيّنhi = mid. - سمِّ الفهرس النهائي
k: فهو يحتوي على أصغر قيمة. - إذا كان
nums[k] ≤ target ≤ nums[n-1]، فابحث في الفهارس منkإلىn-1؛ وإلا فابحث في الفهارس من 0 إلىk-1. - نفّذ بحثًا ثنائيًا عاديًا ضمن هذا النطاق وأعِد فهرس
target، أو-1إذا أصبح النطاق فارغًا.
def search(nums, target):
n = len(nums)
# 1. Find k, the index of the smallest value, where the second run starts.
lo, hi = 0, n - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the drop is right of mid
else:
hi = mid # mid is in the low run: the minimum is at mid or left of it
k = lo
# 2. nums[k..n-1] and nums[0..k-1] are sorted: search the one whose range holds target.
if nums[k] <= target <= nums[n - 1]:
lo, hi = k, n - 1
else:
lo, hi = 0, k - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1بحث ثنائي واحد في النصف المرتب
الفكرة
لا تحتاج إلى معرفة موضع نقطة الدوران. حافظ على الوعد المعتاد للبحث الثنائي: إذا كان target موجودًا في القائمة، فسيكون فهرسه بين lo وhi. انظر إلى الفهرس الأوسط mid. تنخفض القيم مرة واحدة فقط في القائمة كلها، لذا يقع هذا الانخفاض في واحد على الأكثر من النصفين حول mid، ويكون النصف الآخر مرتبًا.
اعثر على النصف المرتب بمقارنة واحدة. إذا كان nums[lo] ≤ nums[mid]، فإن النصف الأيسر nums[lo..mid] لا يتضمن أي انخفاض وهو مرتب. وبما أنك تعرف مسبقًا أن nums[mid] ليس target، فلا يمكن أن يكون target في ذلك النصف إلا إذا كان nums[lo] ≤ target < nums[mid]. إذا تحقق ذلك، فعيّن hi = mid - 1؛ وإذا لم يتحقق، فلا يمكن أن يكون target إلا في النصف الآخر، لذا عيّن lo = mid + 1. عندما يكون nums[lo] > nums[mid]، يكون الانخفاض إلى اليسار، ويكون النصف الأيمن nums[mid..hi] مرتبًا، ويحسم الاختبار المقابل nums[mid] < target ≤ nums[hi] الأمر. لا تستدل مباشرةً على النصف غير المرتب أبدًا: إذ لا يكون target فيه إلا عندما يتعذر وجوده في النصف المرتب.
تتبّع المثال الأول، [15, 19, 23, 2, 5, 8, 11] مع target = 5. يتراوح النطاق من 0 إلى 6، وفهرسه الأوسط 3 وقيمته 2. بما أن 15 أكبر من 2، فإن النصف الأيمن [2, 5, 8, 11] مرتب، وتقع فيه القيمة 5، لذا تصبح قيمة lo هي 4. يتراوح النطاق من 4 إلى 6، وفهرسه الأوسط 5 وقيمته 8. الآن nums[4] = 5 ≤ 8، والنصف الأيسر [5, 8] مرتب ويحتوي على 5، لذا تصبح قيمة hi هي 4. يحتوي الفهرس 4 على القيمة 5: أعد 4.
يُقسّم كل تكرار النطاق إلى النصف، كما في البحث الثنائي العادي، لذا تتكرر الحلقة بحد أقصى نحو log2(n) + 1 مرة: 13 خطوة لـ 5000 عنصر، مع استخدام فهرسين كذاكرة إضافية.
الخوارزمية
- عيّن
lo = 0وhi = n-1. - ما دام
lo ≤ hi، احسبmid. إذا كانتnums[mid]تساويtarget، فأعِدmid. - إذا كان
nums[lo] ≤ nums[mid]، فالنصف الأيسر مرتب: إذا كانnums[lo] ≤ target < nums[mid]فعيّنhi = mid - 1، وإلا فعيّنlo = mid + 1. - وإلا فالنصف الأيمن مرتب: إذا كان
nums[mid] < target ≤ nums[hi]فعيّن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[lo] <= nums[mid]:
# nums[lo..mid] is sorted: target is in it only if it fits its range
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
# nums[mid..hi] is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
أخطاء شائعة وحالات حدّية
البحث ذو المرور الواحد موجز، وتقع جميع الأخطاء تقريبًا في عامل مقارنة.
- كتابة
nums[lo] < nums[mid]بدلًا من≤. عندما يتبقى عنصران، تكونmidمساوية لـlo، ويكون النصف الأيسر مكوّنًا من عنصر واحد، وهو مرتب. مع الاختبار الصارم، تُعامَل[9, 4]وtarget = 4على أن[9, 4]هو النصف الأيمن المرتب، ويُعثَر على 4 خارج النطاق من 9 إلى 4، وتُعاد-1. - مقارنة
targetمعnums[mid]أولًا، كما في البحث الثنائي العادي. في[15, 19, 23, 2, 5, 8, 11]معtarget = 19، تكون القيمة الوسطى 2 أصغر من 19، لذا ينتقل البحث إلى اليمين ولا يصل أبدًا إلى الفهرس 1. - اختبار طرف واحد فقط من النصف المرتب. في
[40, 50, 60, 70, 80, 10, 20]معtarget = 80، تكون القيمة الوسطى 70 ويكون النصف الأيسر[40, 50, 60, 70]مرتبًا. فحصtarget ≥ nums[lo]وحده يوجّه البحث إلى اليسار، لأن 80 أكبر من 40، لكن 80 أكبر أيضًا من 70، لذا فهو يقع في النصف الأيمن. افحص الطرفين. - نسيان الحالة غير المدورة في النهج ذي الخطوتين. عندما تكون
k = 0، يكون التشغيل الثاني فارغًا ونطاقه من0إلى-1. لا بأس بذلك مع الفهارس ذات الإشارة، لكن مع الفهارس غير الموقعة (مثلusizeفي Rust)، يحدث تجاوز عندk - 1، ولهذا يستخدم كود Rust نطاقات نصف مفتوحة. - إرجاع الموضع نفسه في Lua وR. تبدأ القوائم فيهما من 1، لذا اطرح 1 قبل الإرجاع.
أسئلة شائعة4
ما التعقيد الزمني للبحث في مصفوفة مرتبة بعد تدويرها؟
زمن O(log n) ومساحة إضافية O(1). في كل خطوة، يُبقي على نصف النطاق الحالي، تمامًا كما في البحث الثنائي العادي، لذا تحتاج قائمة تضم 5000 عنصر إلى 13 خطوة على الأكثر. الإصدار ذو الخطوتين الذي يجد نقطة الدوران أولًا هو أيضًا O(log n)، ويحتاج إلى ضعف عدد الخطوات تقريبًا.
كيف تعرف أيّ نصف من المصفوفة المُدوَّرة مرتب؟
قارن nums[lo] بـ nums[mid]. تنخفض القيم مرة واحدة فقط في القائمة بأكملها. إذا كان nums[lo] ≤ nums[mid]، فهذا الانخفاض ليس بين lo وmid، لذا فإن النصف الأيسر مرتب. وإلا، فالانخفاض يقع في النصف الأيسر، ما يعني أن النصف الأيمن، من mid إلى hi، لا يحتوي على أي انخفاض وهو مرتب.
هل تعمل الخوارزمية عندما تحتوي المصفوفة على عناصر مكررة؟
ليس بالصيغة المكتوبة. في [1, 0, 1, 1, 1]، تكون القيم nums[lo] وnums[mid] وnums[hi] كلها 1، لذا لا يمكن إثبات أن أيًّا من النصفين مرتب. والحل المعتاد هو تحريك lo إلى الأمام بمقدار واحد عندما تكون nums[lo] وnums[mid] وnums[hi] متساوية، وهذا يحافظ على صحة الإجابة، لكنه يجعل الحالة الأسوأ O(n).
هل ينبغي أن تجد نقطة الدوران أولًا أم تبحث في مرور واحد؟
كلاهما يعمل في O(log n). إن إيجاد فهرس القيمة الصغرى يقسم المسألة أولًا إلى عمليتي بحث ثنائي عاديتين، لذا يعيد كل جزء استخدام شيفرة تثق بها بالفعل. أما البحث بمرور واحد فيؤدي المهمة نفسها ضمن حلقة واحدة وبخطوات أقل، وهو الإصدار الذي يتوقعه معظم المحاوِرين.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def search(nums, target):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
nums = [15, 19, 23, 2, 5, 8, 11] target = 5
المتوقع
4