題目
#

leetcode 33 - Search in Rotated Sorted Array (題目說明請點連結)

題目簡述
#

在一個旋轉排序的陣列中搜尋一個目標值，並返回其索引。如果目標值不存在於陣列中，則返回 -1。可以假設陣列中不存在重複的元素。

範例
#

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

解題思路
#

這題要求我們在一個旋轉排序陣列中搜尋一個目標值，並返回其索引。如果目標值不存在於陣列中，則返回 -1。我們可以使用二分搜尋的方法來解決這個問題，通過比較中間值與左右邊界來判斷哪一部分是有序的，從而縮小搜尋範圍。

解法
#

二分搜尋法（Binary Search Approach）

初始化 left 和 right 指針，分別指向陣列的開頭和結尾
當 left 小於等於 right 時，執行以下步驟：
- 計算中間索引 mid
- 如果中間值等於目標值，返回 mid
- 判斷哪一部分是有序的，並根據目標值調整 left 和 right
如果目標值不存在於陣列中，返回 -1

算法步驟
#

初始化：
- 設定 left 和 right 指針，分別指向陣列的開頭與結尾。
進行二分搜尋：
- 每次計算 mid = left + (right - left) / 2。
- 如果 nums[mid] == target，直接回傳 mid。
- 判斷哪一半是有序的：
  - 若 nums[left] <= nums[mid]，代表左半邊有序。
    - 若 nums[left] <= target < nums[mid]，則目標值在左半邊，right = mid - 1。
    - 否則，目標值在右半邊，left = mid + 1。
  - 否則，右半邊有序。
    - 若 nums[mid] < target <= nums[right]，則目標值在右半邊，left = mid + 1。
    - 否則，目標值在左半邊，right = mid - 1。
返回結果：
- 若找到目標值則回傳其索引，否則回傳 -1。

例子說明
#

nums = [4,5,6,7,0,1,2], target = 0

步驟	left	right	mid	nums[mid]	操作說明
初始化	0	6	3	7	設定`left=0`、`right=6`，計算`mid=3`，nums[mid]=7。判斷左半邊`[4,5,6,7]`是有序的。因為`target=0`不在這個區間，所以將`left`移到`mid+1=4`。
第1輪	4	6	5	1	重新計算`mid=5`，nums[mid]=1。右半邊`[1,2]`是有序的。但`target=0`小於`nums[mid]=1`，所以將`right`移到`mid-1=4`。
第2輪	4	4	4	0	只剩一個元素，`mid=4`，nums[mid]=0。這時`nums[mid]`剛好等於`target`，所以回傳索引`4`。

完整程式碼
#

java

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        // 使用二分搜尋法
        while(left <= right){
            int mid = left + (right - left) / 2;

            // 如果找到目標值，返回索引
            if(nums[mid] == target){
                return mid;
            }

            // 判斷哪一部分是有序的
            if(nums[left] <= nums[mid]){
                // 左半部分有序
                if(nums[mid] > target && target >= nums[left]){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }else{
                // 右半部分有序
                if(nums[right] >= target && target > nums[mid]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }

        // 如果目標值不存在，返回 -1
        return -1;
    }
}