原文題目

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

題目摘要

1. Input陣列為已升序排列的陣列再經旋轉而得
2. 題目所求：回傳位於新陣列中target的索引值

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. 設定左右指標：
   • 首先，設定left和right指標分別為陣列第一位和最後一位。
2. 找到中間點：
   • 我們在給定的陣列中找出中間點的元素 mid。
3. 判斷哪一部分是有序的：
   • 如果 nums[left] <= nums[mid]，說明左半部分是有序的。
   • 如果 nums[mid] <= nums[right]，說明右半部分是有序的。
4. 決定在哪一部分進行搜尋：
   • 如果左半部分有序，且目標值 target 落在 nums[left] 到 nums[mid] 之間，那麼我們應該在左半部分繼續搜尋；否則，就在右半部分搜尋。
   • 如果右半部分有序，且目標值 target 落在 nums[mid] 到 nums[right] 之間，那麼我們應該在右半部分繼續搜尋；否則，就在左半部分搜尋。
5. 重複以上步驟：
   • 根據以上的判斷，我們不斷縮小搜尋範圍，直到找到目標值 target 或者搜尋範圍縮小到無法再縮小為止。
6. 結束條件：
   • 如果找到了目標值，則返回其索引；如果沒有找到，則返回 -1。

程式碼

class Solution {
    public int search(int[] nums, int target) {
        int left = 0; //設立左指標為陣列第一位，索引值為0
        int right = nums.length - 1; //設立右指標為陣列最後一位，索引值為陣列長-1

        while (left <= right) {
            int mid = (left + right) / 2; //設定中間值
            //當中間值即為目標值則回傳中間值索引
            if (nums[mid] == target) {
                return mid;
            } 
            //假設mid左側已排序
            else if (nums[mid] >= nums[left]) {
                //確定在左側，目標值介於左指標與中間值之間
                if (nums[left] <= target && target <= nums[mid]) {
                    right = mid - 1; //將範圍限制在左指標與中間值前一位（新右指標）
                } 
                else {
                    left = mid + 1; //將範圍限制在中間值後一位（新左指標）與右指標
                }
            } 
            //假設mid右側已排序
            else {
                //確定在右側，目標值介於中間值與右指標之間
                if (nums[mid] <= target && target <= nums[right]) {
                    left = mid + 1; //將範圍限制在中間值後一位（新左指標）與右指標
                } 
                else {
                    right = mid - 1; //將範圍限制在左指標與中間值前一位（新右指標）
                }
            }
        return -1; //若陣列不含目標值則回傳-1       
    }
}

結論

這題旋轉排序陣列的問題，其實就像我們在生活中遇到一個「亂序」的書架。我們明明知道書是按順序排好的，但有一部分書被移動到了另一個地方。我們要在這個「亂序」的書架上找一本書，最好的方法就是從中間開始，快速縮小範圍。這題的解法運用了二分搜尋，透過判斷中間書的位置來決定下一步是往左還是往右找。這個技巧在處理部分有序但被打亂的資料中就像快速找到移動過的書一樣，是一個非常實用的演算法。