62. Search in Rotated Sorted Array【medium】

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e.,?0 1 2 4 5 6 7?might become?4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Have you met this question in a real interview?? Yes Example

For?[4, 5, 1, 2, 3]?and?target=1, return?2.

For?[4, 5, 1, 2, 3]?and?target=0, return?-1.

Challenge?

O(logN) time

?

錯誤解法：

1 class Solution { 2 public: 3 /* 4 * @param A: an integer rotated sorted array 5 * @param target: an integer to be searched 6 * @return: an integer 7 */ 8 int search(vector<int> A, int target) { 9 if (A.size() == 0) { 10 return -1; 11 } 12 13 int start = 0; 14 int end = A.size() - 1; 15 16 while (start + 1 < end) { 17 int mid = start + (end - start) / 2; 18 19 if (A[mid] == target) { 20 return mid; 21 } 22 else if (A[mid] < target) { 23 // 5 6 1 2 3 4 24 if (A[mid] > A[start]) { 25 start = mid; 26 } 27 // 5 6 1 2 3 4 28 else { // mid < target && mid <= start 29 end = mid; 30 } 31 } 32 else if (A[mid] > target) { 33 34 if (A[mid] < A[end]) { // mid > target && mid < end 35 end = mid; 36 } 37 // 3 4 5 6 1 2 找3 38 else { // mid > target && mid >= end 39 start = mid; 40 } 41 } 42 } 43 44 if (A[start] == target) { 45 return start; 46 } 47 48 if (A[end] == target) { 49 return end; 50 } 51 52 return -1; 53 } 54 };

一開始思考的方向就不對，搞暈了……

?

解法一：

1 class Solution { 2 public: 3 /* 4 * @param A: an integer rotated sorted array 5 * @param target: an integer to be searched 6 * @return: an integer 7 */ 8 int search(vector<int> A, int target) { 9 if (A.size() == 0) { 10 return -1; 11 } 12 13 int start = 0; 14 int end = A.size() - 1; 15 16 while (start + 1 < end) { 17 int mid = start + (end - start) / 2; 18 19 if (A[mid] == target) { 20 return mid; 21 } 22 23 if (A[mid] >= A[start]) { 24 if (A[start] <= target && target <= A[mid]) { 25 end = mid; 26 } 27 else { 28 start = mid; 29 } 30 } 31 else { 32 if (A[mid] <= target && target <= A[end]) { 33 start = mid; 34 } 35 else { 36 end = mid; 37 } 38 } 39 } 40 41 if (A[start] == target) { 42 return start; 43 } 44 45 if (A[end] == target) { 46 return end; 47 } 48 49 return -1; 50 } 51 };

借鑒網上的一個圖，可以清楚的歸納一下思路，那么代碼就好寫了。

這個圖參考了：http://fisherlei.blogspot.com/2013/01/leetcode-search-in-rotated-sorted-array.html

?

解法二：

1 class Solution { 2 public: 3 int search(int A[], int n, int target) { 4 return searchRotatedSortedArray(A, 0, n-1, target); 5 } 6 7 int searchRotatedSortedArray(int A[], int start, int end, int target) { 8 if(start>end) return -1; 9 int mid = start + (end-start)/2; 10 if(A[mid]==target) return mid; 11 12 if(A[mid]<A[end]) { // right half sorted 13 if(target>A[mid] && target<=A[end]) 14 return searchRotatedSortedArray(A, mid+1, end, target); 15 else 16 return searchRotatedSortedArray(A, start, mid-1, target); 17 } 18 else { // left half sorted 19 if(target>=A[start] && target<A[mid]) 20 return searchRotatedSortedArray(A, start, mid-1, target); 21 else 22 return searchRotatedSortedArray(A, mid+1, end, target); 23 } 24 } 25 };

?

解法三：

1 class Solution { 2 public: 3 int search(int A[], int n, int target) { 4 int start = 0, end = n-1; 5 while(start<=end) { 6 int mid = start + (end-start)/2; 7 if(A[mid]==target) return mid; 8 9 if(A[mid]<A[end]) { // right half sorted 10 if(target>A[mid] && target<=A[end]) 11 start = mid+1; 12 else 13 end = mid-1; 14 } 15 else { // left half sorted 16 if(target>=A[start] && target<A[mid]) 17 end = mid-1; 18 else 19 start = mid+1; 20 } 21 } 22 return -1; 23 } 24 };

解法二和解法三參考了：http://bangbingsyb.blogspot.com/2014/11/leetcode-search-in-rotated-sorted-array.html

思路如下：

題目一看就知道是binary search。所以關鍵點在于每次要能判斷出target位于左半還是右半序列。解這題得先在紙上寫幾個rotated sorted array的例子出來找下規律。Rotated sorted array根據旋轉得多少有兩種情況：

原數組：0 1 2 4 5 6 7
情況1： ?6?7 0?1?2 4?5 ? ?起始元素0在中間元素的左邊
情況2： ?2?4 5?6?7 0?1 ? ?起始元素0在中間元素的右邊

兩種情況都有半邊是完全sorted的。根據這半邊，當target != A[mid]時，可以分情況判斷：

當A[mid] < A[end] < A[start]：情況1，右半序列A[mid+1 : end]?sorted
A[mid] < target <= A[end], 右半序列，否則為左半序列。

當A[mid] > A[start] > A[end]：情況2，左半序列A[start : mid-1] sorted
A[start] <= target < A[mid], 左半序列，否則為右半序列

最后總結出：
A[mid] = ?target, 返回mid，否則

(1) A[mid] < A[end]: A[mid+1 : end] sorted
A[mid] < target <= A[end] ?右半，否則左半。

(2) A[mid] > A[end] : A[start : mid-1] sorted
A[start] <= target < A[mid] 左半，否則右半。

?

?

?

?

轉載于:https://www.cnblogs.com/abc-begin/p/7552275.html

總結

以上是生活随笔為你收集整理的62. Search in Rotated Sorted Array【medium】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。