## 一.題目描述  ## 二.解題技巧 由于這道題出現了旋轉的情況，即比第一個元素小的元素可能出現在數值的后半段或者不出現。因此，可以考慮采用變種的二分查找，即在比較中間元素與目標之前，先比較第一個元素與目標的關系，這個時候，會出現三種情況： 1.第一個元素剛好等于目標，返回第一個元素的坐標，函數結束；? 2.第一個元素大于目標，那么目標就可能存在被旋轉到數組后面的情況，這個時候，還要比較與數組中間元素的關系，這個時候又會有三種情況： ~~~ a.中間元素大于第一個元素，這個時候，目標可能存在于數組的后半段中，遞歸調用函數，尋找目標的坐標； b.中間元素等于目標，返回中間元素的坐標，函數結束； c.中間元素小于第一個元素，這個時候，又可以分為兩種情況進行： (1).中間元素小于目標元素，那么目標元素可能存在于數組的后半段中，遞歸調用函數，尋找目標的坐標； (2).中間元素大于目標元素，那么目標元素可能存在于數組的前半段中，遞歸調用函數，尋找目標的坐標； ~~~ 3.第一個元素小于目標，這是也有三種情況需要考慮： ~~~ a.中間元素等于目標元素，返回中間元素的坐標，函數結束； b.中間元素大于第一個元素，這個時候，也有兩種情況要考慮： (1).中間元素大于目標，那么目標元素可能存在于數組的前半段中，遞歸調用函數，尋找目標的坐標； (2).中間元素小于目標，那么目標元素可能存在于數組的后半段中，遞歸調用函數，尋找目標的坐標； c.中間元素小于第一個元素，那么目標元素可能存在于數組的前半段中，遞歸調用函數，尋找目標的坐標； ~~~ 當然，還需要考慮數組的元素個數為0，1, 2,的情況，以及對于遞歸的過程中數組的起始位置坐標以及數組中元素的個數，這些才是這道題的難點所在，我也是調試了很久才調通代碼的。 ## 三.示例代碼 ~~~ // 時間復雜度O(log n)，空間復雜度O(1) #include <iostream> using namespace std; class Solution { public: int SearchRotatedSortedArray(int A[], int n, int target) { int start = 0; int end = n; int middle = start + (end - start) / 2; while (start != end) { if (target == A[middle]) return middle; if (A[start] < A[middle]) { if ((target < A[middle]) && (A[start] <= target)) end = middle; else start = middle + 1; } else { if ((target > A[middle]) && (target <= A[end - 1])) start = middle + 1; else end = middle; } } return -1; // 在數組中找不到目標元素時返回-1 } }; ~~~ ## 四.體會 這答題的難點在于邊界條件和遞歸過程中的數組的第一個元素的指針設置和數組元素個數的設置上面，邊界條件經常是面試題考查的重點。