1 題目

??在旋轉排序數組中查找元素（Search in Rotated Sorted Array）

lintcode：題號——62，難度——medium

2 描述

??給定一個有序數組，但是數組以某個元素作為支點進行了旋轉(比如，0 1 2 4 5 6 7 可能成為4 5 6 7 0 1 2)。給定一個目標值target進行搜索，如果在數組中找到目標值返回數組中的索引位置，否則返回-1。你可以假設數組中不存在重復的元素。

??名詞：

RSA：旋轉排序數組，即Rotated Sorted Array

??樣例1：

輸入：數組 = [4, 5, 1, 2, 3]，target = 1
輸出：2
解釋：

元素1在數組中對應索引位置為2。

??樣例2：

輸入：數組 = [4, 5, 1, 2, 3]，target = 0
輸出：-1
解釋：

元素0不在數組中，返回-1。

3 思路

??因為RSA是分段有序的，要在RSA里查找某個值，之前有一題是尋找RSA中的最小值^[1]，可以通過找到最小值將RSA分為兩段標準的有序數組，然后再進行二分查找來得到結果，這種方式的時間復雜度是兩輪二分搜索O(log n) * 2，依舊是O(log n)。
??第二種思路是通過拋掉不可能存在目標元素的區間，來不斷縮小目標區間的思想，即“half half”的方式，在RSA數組（假設未旋轉前的原數組為升序）的中點切一刀，考慮RSA數組的特點，數組被最小值分為上半區間和下半區間，中點位置有兩種情況，第一，中點元素在上半區間（升序RSA的上半區間在左邊），這種情況下，如果起點元素 <= 目標元素值 <= 中點元素，則目標元素不可能在中點右邊，拋掉右邊，反之則拋掉左邊；第二，中點元素在下半區間，這種情況下，如果中點元素 <= 目標元素值 <= 結尾元素，則目標元素不可能在中點左邊，拋掉左邊，反之則拋掉右邊。而判斷中點在上半區還是下半區的方式，可以通過比較中點元素值與起點元素值或者結尾元素值的大小來得到。使用以上方式來不斷縮小目標區間，直到找到目標或者目標元素不存在。使用第二種思路來解題。

1. 取中點；
2. 判斷中點元素值與結尾元素值的大小，找出中點屬于上半區間還是下半區間；
3. 上半區間：起點元素 <= 目標元素值 <= 中點元素，成立則取左，不成立取右。
4. 下半區間：中點元素 <= 目標元素值 <= 結尾元素，成立則取右，不成立取左。
5. 重復以上步驟，直到找到目標或者目標元素不存在。

3.1 圖解

輸入：數組 = [4, 5, 6, 7, 8, 9, 0, 1, 2, 3]，target = 9
輸出：5

元素9在數組中對應索引位置為5

3.2 時間復雜度

??算法的時間復雜度為O(log n)。

3.3 空間復雜度

??算法的空間復雜度為O(1)。

4 源碼

??注意事項：

1. 如果每次循環都進行目標值判斷，可以在中途找到目標元素的時候直接返回，即可得到結果，不用等待二分搜索結束；
2. 如果每次循環不進行目標值判斷，則需要在內層的條件判斷上考慮邊界；
3. 返回的是序號，不是元素值。

??C++版本：

/**
* @param A: RSA數組
* @param target: 需要查找的目標值
* @return: 目標值的索引
*/
int search(vector<int> &A, int target) {
        // write your code here
        if (A.empty())
        {
            return -1;
        }

        int start = 0;
        int end = A.size() - 1;
        int mid = 0;
        while (start + 1 < end)
        {
            mid = start + (end - start) / 2;
            // 這里三個if是每次循環進行判斷，為了加速搜索，如果當前已經找到目標值，直接返回，不用等到二分搜索結束
            if (A.at(start) == target)
            {
                return start;
            }
            if (A.at(mid) == target)
            {
                return mid;
            }
            if (A.at(end) == target)
            {
                return end;
            }

            if (A.at(mid) > A.at(end)) // 判斷中點是否在上半區間
            {
                // 如果沒有上面的三個if，此處的“<”、“>”都應該考慮邊界，變為“<=”、“>=”
                if (A.at(start) < target && A.at(mid) > target) 
                {
                    end = mid;
                }
                else
                {
                    start = mid;
                }
            }
            if (A.at(mid) < A.at(end)) // 判斷中點是否在下半區間
            {
                // 如果沒有上面的三個if，此處的“<”、“>”都應該考慮邊界，變為“<=”、“>=”
                if (A.at(mid) < target && A.at(end) > target)
                {
                    start = mid;
                }
                else
                {
                    end = mid;
                }
            }
        }

        if (A.at(start) == target)
        {
            return start;
        }
        if (A.at(end) == target)
        {
            return end;
        }

        return -1;
    }