LintCode領扣 題解丨微軟高頻題：搜尋旋轉排序數組

假設有一個排序的按未知的旋轉軸旋轉的數組(比如，0 1 2 4 5 6 7 可能成為4 5 6 7 0 1 2)。給定一個目标值進行搜尋，如果在數組中找到目标值傳回數組中的索引位置，否則傳回-1。你可以假設數組中不存在重複的元素。

線上評測位址：

https://www.lintcode.com/problem/search-in-rotated-sorted-array/?utm_source=sc-tianchi-sz0827

例1:

輸入: [4, 5, 1, 2, 3] and target=1,

輸出: 2.

例2:

輸入: [4, 5, 1, 2, 3] and target=0,

輸出: -1.

【題解】

算法：二分

根據題目我們可以知道旋轉數組實際上是兩個遞增數組的組成，且第一個數組中的最小值大于第二個數組的最大值

由于數組中不存在重複的元素，那麼我們可以先找到target在哪個數組，再進行二分

代碼思路

二分找到第二個數組的起始位置，即整個數組的最小值的位置minPosition

通過比較target和第二個數組最小元素（即最後一個數）大小關系判斷target在哪一個數組

對target所在的數組二分

複雜度分析

N表示為 A 數組的長度

空 間複雜度：O(N)

時間複雜度：O(logN)

public class Solution {

/**
 * @param A: an integer rotated sorted array
 * @param target: an integer to be searched
 * @return: an integer
 */
public int search(int[] A, int target) {
    if (A == null || A.length == 0) { 
        return -1; 
    } 
        
    //找到數組最小值位置minPosition，即第二個數組的起始位置
    int minPosition = 0; 
    intleft = 0; 
    int right = A.length - 1; 
    while (left + 1 < right) { 
        int mid = left + (right - left) / 2; 
        if (A[mid] > A[right]) { 
           left = mid; 
        } else { 
            right = mid; 
        } 
    }         
         
    if (A[left] < A[right]) { 
        minPosition = left; 
    } else { 
        minPosition = right; 
    } 
         
    //判斷target在哪一個數組中
    if (A[A.length - 1] < target) { 
        left = 0; 
        right = minPosition - 1; 
    } else { 
        left = minPosition; 
        right = A.length - 1; 
    }
         
    //對target所在數組二分搜尋
    while (left + 1 < right) { 
        int mid = left + (right - left) / 2; 
        if (A[mid] < target) { 
            left = mid; 
        } else { 
            right = mid; 
        } 
    }          
        
    if (A[left] == target) { 
        return left; 
    } 
    if (A[right] == target) { 
        return right; 
    }         
    return -1; 
}           

}

更多題解參見九章算法官網：

https://www.jiuzhang.com/solution/search-in-rotated-sorted-array/?utm_source=sc-tianchi-sz0827