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
- الشرح
- العنصر الأوسط الأول، عند الفهرس 3، يحتوي على 2، لذا فإن النصف الأيمن
[2, 5, 8, 11]مرتب ويحتوي على 5. العنصر الأوسط التالي، عند الفهرس 5، يحتوي على 8؛ والجزء الأيسر المرتب[5, 8]يحتوي على 5، ما يؤدي إلى الفهرس 4.
- المدخلات
- nums = [40, 50, 60, 70, 10, 20, 30]target = 65
- المخرجات
- -1
- الشرح
- ينبغي أن يقع 65 بين 60 و70، ولا يحتوي عليه أي عنصر. يضع الوسط الأول، 70، العدد 65 داخل الجزء الأيسر المرتب
[40, 50, 60, 70]، ويضيق النطاق هناك حتى يصبح فارغًا.
- المدخلات
- nums = [8, 13, 21, 1, 3, 5]target = 13
- المخرجات
- 1
- الشرح
- العنصر الأوسط الأول، عند الفهرس 2، يحتوي على 21. الجزء الأيسر
[8, 13, 21]مرتب، وتقع 13 بين 8 و21، لذا يُستبعَد الجزء الأيمن. ثم يعثر البحث على 13 عند الفهرس 1.
سؤال إضافي
إذا كان من الممكن أن تحتوي nums على قيم مكررة، فلا يمكن لأي خوارزمية أن تضمن O(log n). هل يمكنك إثبات ذلك باستخدام قائمة مُدوَّرة من قيم 1 تخفي قيمة 0 واحدة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
اختر أي فهرس في المنتصف وانظر إلى النصفين على جانبيه. أنشأ التدوير موضعًا واحدًا تنخفض فيه القيم من الأكبر إلى الأصغر. هل يمكن أن يحتوي كلا النصفين على هذا الانخفاض؟
يكون نصف واحد على الأقل مرتبًا دائمًا، وتخبرك مقارنة
nums[lo]بـnums[mid]أيَّ النصفين هو المرتب. وبالنسبة إلى النصف المرتب، يمكنك التحقق بخطوة واحدة مما إذا كانtargetيقع بين قيمته الأولى والأخيرة.أبقِ
loوhiحول الجزء الذي لا يزال من الممكن أن يحتوي علىtarget. في كل خطوة، إذا كان نطاق القيم في النصف المرتب يحتوي علىtarget، فأبقِ ذلك النصف؛ وإلا فأبقِ النصف الآخر. توقّف عندما تجدtargetأو يصبح النطاق فارغًا.
الحل
القائمة المرتبة بعد تدويرها تتكوّن من مقطعين مرتبين: [15, 19, 23] ثم [2, 5, 8, 11]. لم تعد مقارنة target بالقيمة الوسطى تخبرك في أي جانب توجد. لكن أينما قسمت القائمة، يكون أحد النصفين مرتبًا على الأقل، وتخبرك مقارنة واحدة ما إذا كان من الممكن أن تكون target في ذلك النصف.
افحص كل عنصر
الفكرة
تحقّق من كل فهرس وأعِد أول فهرس تكون قيمته مساوية لـ target، أو -1 بعد انتهاء الحلقة. تقرأ هذه الطريقة كل عنصر، لذا فهي صحيحة لأي قائمة. لكنها تتجاهل الجزأين المرتّبين: يتطلّب البحث في 5000 عنصر ما يصل إلى 5000 مقارنة، بينما يحتاج البحث الثنائي إلى 13 مقارنة.
الخوارزمية
- لكل فهرس
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. كلٌّ من nums[k..n-1] وnums[0..k-1] مرتّب، وكل قيمة في المقطع الأول أكبر من كل قيمة في المقطع الثاني. بمجرد أن تعرف k، تحدد مقارنة target مع nums[k] وnums[n-1] المقطع المناسب، ثم يُكمل البحث الثنائي العادي المهمة.
لإيجاد k، قارن القيمة الوسطى مع nums[hi]. إذا كان nums[mid] > nums[hi]، فهذا يعني أن القيم تنخفض في موضع ما بعد mid، لذا يكون الحد الأدنى على يمينه. وإلا فإن nums[mid..hi] تتزايد دون انخفاض، لذا يكون الحد الأدنى عند mid أو قبله. في المثال الأول، تكون القيم الوسطى 2 و19 و23، ما يعطي k = 3، وتقع 5 بين nums[3] = 2 وnums[6] = 11. يستغرق بحثان ثنائيان نحو 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. - أعِد الفهرس الذي عُثر عليه، أو
-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 على موضع الانخفاض، بينما يكون النصف الآخر مرتبًا. إذا كان nums[lo] ≤ nums[mid]، فالنصف الأيسر مرتب؛ وإلا فالنصف الأيمن هو المرتب.
بالنسبة إلى النصف المرتب، يحدد اختبار النطاق عند طرفيه ما إذا كان من الممكن أن يكون target داخله، مثلًا nums[lo] ≤ target < nums[mid] في النصف الأيسر. إذا كان ذلك ممكنًا، فابحث فيه؛ وإذا لم يكن، فلا يمكن أن يكون target إلا في النصف الآخر. في كل خطوة، ينقسم النطاق إلى النصف: 13 خطوة على الأكثر لـ 5000 عنصر.
الخوارزمية
- عيّن
lo = 0وhi = n-1. - ما دام
lo ≤ hi، احسبmidوأعِده إذا كانتnums[mid]تساويtarget. - إذا كان
nums[lo] ≤ nums[mid]، فإن النصف الأيسر مرتب: عيّنhi = mid - 1عندماnums[lo] ≤ target < nums[mid]، وإلا فعيّنlo = mid + 1. - وإلا فإن النصف الأيمن مرتب: عيّن
lo = mid + 1عندماnums[mid] < target ≤ nums[hi]، وإلا فعيّن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إلى إرجاع-1. - مقارنة
targetمعnums[mid]أولًا. في المثال الأول معtarget = 19، يكون العنصر الأوسط 2 أصغر، لذا ينتقل البحث إلى اليمين ويفوّت الفهرس 1. - اختبار أحد طرفي النصف المرتب فقط. في
[40, 50, 60, 70, 80, 10, 20]معtarget = 80، يؤديtarget ≥ nums[lo]وحده إلى توجيه البحث إلى[40, 50, 60, 70]. - في Rust، يحدث تجاوز سفلي عند استخدام
k - 1على قيمة من النوعusizeعندما تكونk = 0، أي في القائمة غير المُدارة التدوير. استخدم نطاقات مفتوحة من الطرفين. - في Lua وR، إرجاع الموضع ذي الفهرسة التي تبدأ من 1. اطرح 1.
أسئلة شائعة3
ما هو التعقيد الزمني للبحث في مصفوفة مرتبة ومدوّرة؟
زمن O(log n) ومساحة إضافية O(1). تحتفظ كل خطوة بنصف النطاق، لذا تحتاج 5000 عنصر إلى 13 خطوة كحد أقصى. العثور على نقطة الدوران أولًا يستغرق أيضًا O(log n)، مع عدد خطوات يقارب الضعف.
هل تعمل الخوارزمية عندما تحتوي المصفوفة على عناصر مكررة؟
ليس بهذه الصيغة. عندما تكون nums[lo] وnums[mid] وnums[hi] متساوية، لا يمكن إثبات أن أيًّا من النصفين مرتب. والحل المعتاد هو تحريك lo إلى الأمام بمقدار واحد في هذه الحالة، ما يحافظ على صحة الإجابة لكنه يجعل أسوأ حالة O(n).
هل ينبغي أن تجد نقطة الدوران أولًا أم تبحث في مرور واحد؟
كلاهما يعمل في O(log n). العثور على الحد الأدنى أولًا يقسّم المسألة إلى عمليتي بحث ثنائي عاديتين. ينجز البحث في مرور واحد المهمة ضمن حلقة واحدة وبخطوات أقل، وهو الإصدار الذي يتوقعه معظم القائمين على المقابلات.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def search(nums, target):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
nums = [15, 19, 23, 2, 5, 8, 11] target = 5
الإخراج المتوقع
4