什麼是旋轉排序數組？

考慮一個排序數組，例如：

[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() 函數來找出 pivot。 
根據主元的位置，我們決定使用二分搜尋來搜尋陣列的哪一半。 


binarySearch():

標準二分搜尋演算法，用於在排序的子數組中尋找目標。 
我們定義開始和結束索引並逐漸縮小搜尋空間。 


searchPivot():

此函數標示樞軸點（陣列旋轉的地方）。 
主元是排序順序被「破壞」的索引（即陣列從較高的值變為較低的值）。 
如果沒有找到樞軸，表示陣列沒有旋轉，我們可以進行常規的二分查找。 


  
  
  演算法如何運作


對於像 [4, 5, 6, 1, 2, 3] 這樣的陣列：

• 樞軸位於索引 2（6 是最大的，其後是 1，最小的）。
• 我們使用這個主元將陣列分成兩部分：[4, 5, 6] 和 [1, 2, 3]。
• 如果目標大於或等於第一個元素（本例為 4），我們將搜尋左半部。否則，我們搜尋右半部分。

此方法確保我們有效率地搜索，實現 O(log n) 的時間複雜度，類似於標準二分搜尋。

結論

旋轉排序數組是常見的面試問題，也是加深您對二分搜尋理解的有用挑戰。透過找到樞軸並相應地調整我們的二分搜索，我們可以在對數時間中有效地搜索數組。

如果您發現本文有幫助，請隨時在 LinkedIn 上與我聯繫或在評論中分享您的想法！快樂編碼！