لماذا وكيف ؟

أثناء قيامي بحل السؤال على leetcode والذي ينص على مجموعة محددة من الأعداد الصحيحة مرتبة بترتيب غير تنازلي، ابحث عن موضع البداية والنهاية لقيمة مستهدفة معينة. لذلك كان من المستحيل إرجاع بداية ونهاية العنصر المستهدف في مصفوفة ذات عملية سكار ثنائية بسيطة لأنها تُرجع فقط الفهرس حيث وجدت العنصر المستهدف الأول الذي يمكن أن يكون أي شيء أول أو نهاية أو وسط هذا العنصر. لذلك نستخدم Double Binary Scarch، وإليك كيفية القيام بذلك...

يقترب

1. البحث الثنائي الأول:

   • قم بإجراء بحث ثنائي للعثور على آخر تواجد للهدف.
   • ابدأ بـ si (فهرس البداية) عند 0 وei (فهرس النهاية) عند nums.length - 1.
   • إذا كان العنصر الأوسط nums[mid] أقل من الهدف، فانقل مؤشر البداية si إلى mid 1 للبحث في النصف الأيمن.
   • إذا كان أكبر من الهدف، حرك مؤشر النهاية ei إلى المنتصف - 1 للبحث في النصف الأيسر.
   • إذا كان nums[mid] يساوي الهدف، قم بتعيين res[1] إلى mid (النهاية الحالية للنطاق) واستمر في البحث في النصف الأيمن (si = mid 1) للعثور على التواجد الأخير.

2. البحث الثنائي الثاني:

   • قم بإجراء بحث ثنائي آخر للعثور على التواجد الأول للهدف.
   • إعادة تعيين si إلى 0 وei إلى nums.length - 1.
   • اتبع أسلوبًا مشابهًا كما كان من قبل، ولكن إذا كان nums[mid] يساوي الهدف، فاضبط res[0] على mid (البداية الحالية للنطاق) واستمر في البحث في النصف الأيسر (ei = mid - 1) إلى العثور على التواجد الأول.

3. نتيجة العودة:

   • تحتوي دقة المصفوفة الناتجة على مؤشرات البداية والنهاية للقيمة المستهدفة.

تعقيد

• تعقيد الوقت:

  • يستغرق البحث الثنائي عن التكرارات الأولى والأخيرة وقتًا O(log n). نظرًا لأننا نقوم بإجراء بحثين ثنائيين، فإن التعقيد الزمني الإجمالي هو O(log n).

• تعقيد الفضاء:

  • O(1) لأننا نستخدم مقدارًا ثابتًا من المساحة الإضافية للمتغيرات.

شفرة

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int ei = nums.length - 1;
        int si = 0;
        int[] res = {-1, -1};  // Initialize result array

        // First binary search to find the last occurrence
        while (si  nums[mid]) {
                si = mid   1;
            } else {
                res[1] = mid;  // Update end index
                si = mid   1;  // Search in the right half
            }
        }

        // Reset the pointers for the second binary search
        si = 0;
        ei = nums.length - 1;

        // Second binary search to find the first occurrence
        while (si  nums[mid]) {
                si = mid   1;
            } else {
                res[0] = mid;  // Update start index
                ei = mid - 1;  // Search in the left half
            }
        }

        return res;  // Return the result array
    }
}