ما هي المصفوفة المرتبة المُدارة؟

فكر في مصفوفة مرتبة، على سبيل المثال:

[1, 2, 3, 4, 5, 6]

الآن، إذا تم تدوير هذه المصفوفة عند نقطة محورية، على سبيل المثال عند الفهرس 3، فإنها ستصبح:

[4, 5, 6, 1, 2, 3]

لاحظ أن المصفوفة لا تزال مرتبة، ولكنها مقسمة إلى قسمين. هدفنا هو البحث عن قيمة مستهدفة في مثل هذه المصفوفات بكفاءة.

استراتيجية البحث

للبحث في مصفوفة مرتبة، نحتاج إلى:

1. البحث عن المحور: المحور هو النقطة التي ينتقل فيها المصفوفة من القيم الأكبر إلى القيم الأصغر.
2. البحث الثنائي: بمجرد العثور على المحور، يمكننا استخدام البحث الثنائي في النصف المناسب من المصفوفة.

شرح التعليمات البرمجية خطوة بخطوة

class Solution {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 1, 2, 3}; // Example of rotated sorted array
        int target = 5;

        // Searching for the target
        int result = search(arr, target);

        // Displaying the result
        System.out.println("Index of target: "   result);
    }

    // Main search function to find the target in a rotated sorted array
    public static int search(int[] nums, int target) {
        // Step 1: Find the pivot
        int pivot = searchPivot(nums);

        // Step 2: If no pivot, perform regular binary search
        if (pivot == -1) {
            return binarySearch(nums, target, 0, nums.length - 1);
        }

        // Step 3: If the target is at the pivot, return the pivot index
        if (nums[pivot] == target) {
            return pivot;
        }

        // Step 4: Decide which half of the array to search
        if (target >= nums[0]) {
            return binarySearch(nums, target, 0, pivot - 1); // Search left side
        } else {
            return binarySearch(nums, target, pivot   1, nums.length - 1); // Search right side
        }
    }

    // Binary search helper function
    static int binarySearch(int[] arr, int target, int start, int end) {
        while (start  arr[mid   1]) {
                return mid;
            }

            // Check if the pivot is before the mid
            if (mid > start && arr[mid] 





  
  
  شرح الكود



يبحث():

هذه الوظيفة مسؤولة عن البحث عن الهدف في المصفوفة المرتبة التي تم تدويرها.
أولاً، نجد المحور باستخدام وظيفة searchPivot().
اعتمادًا على موضع المحور، نقرر بعد ذلك أي نصف المصفوفة سيتم البحث فيه باستخدام البحث الثنائي.


binarySearch():

خوارزمية بحث ثنائية قياسية للعثور على الهدف في مصفوفة فرعية مرتبة.
نحدد مؤشرات البداية والنهاية ونضيق مساحة البحث تدريجياً.


searchPivot():

تحدد هذه الوظيفة النقطة المحورية (المكان الذي يدور فيه المصفوفة).
المحور هو الفهرس الذي "ينكسر" فيه الترتيب المفرز (أي ينتقل المصفوفة من قيمة أعلى إلى قيمة أقل).
إذا لم يتم العثور على أي محور، فهذا يعني أن المصفوفة لم يتم تدويرها، ويمكننا إجراء بحث ثنائي عادي.


  
  
  كيف تعمل الخوارزمية


بالنسبة لمصفوفة مثل [4، 5، 6، 1، 2، 3]:

• يوجد المحور عند الفهرس 2 (6 هو الأكبر، ويتبعه 1، الأصغر).
• نستخدم هذا المحور لتقسيم المصفوفة إلى قسمين: [4, 5, 6] و [1, 2, 3].
• إذا كان الهدف أكبر من أو يساوي العنصر الأول (4 في هذه الحالة)، فإننا نبحث في النصف الأيسر. وإلا فإننا نبحث في النصف الأيمن.

تضمن هذه الطريقة أننا نبحث بكفاءة، مما يحقق تعقيدًا زمنيًا قدره O(log n)، على غرار البحث الثنائي القياسي.

خاتمة

تعد المصفوفات المصنفة التي تم تدويرها سؤالًا شائعًا في المقابلة وتحديًا مفيدًا لتعميق فهمك للبحث الثنائي. من خلال العثور على المحور وتكييف بحثنا الثنائي وفقًا لذلك، يمكننا البحث بكفاءة عبر المصفوفة في الوقت اللوغاريتمي.

إذا وجدت هذه المقالة مفيدة، فلا تتردد في التواصل معي على LinkedIn أو مشاركة أفكارك في التعليقات! برمجة سعيدة!