首页 > 代码库 > leetcode第32题--Search in Rotated Sorted Array
leetcode第32题--Search in Rotated Sorted Array
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.
题目意思是，原先排好序的，然后右移一定位数，在变换后的array中找到给定值改变之后的下标。如果直接扫描一次的话也能Accept，这就失去了出题的意义。题目是想让我们用二分法。在O(logn)的复杂度下实现，而非n复杂度。
这个人解释的不错如下（先陈述他的解释和代码，我之后再给修正）：
下面是rotate后的一个有序数组的图。四边形的斜边表示数组中数值的大小。
在这种情况下数组分了两部分，分别都是有序（递增）的。
当我们计算了Mid以后，有两种可能，分别用Mid1和Mid2表示。
1. 如果A[Low] < A[Mid]，说明Mid落在区间1中,即图中Mid1的位置。那么，如果target小于A[Mid1]，那么继续在Low和Mid1中间搜索；否则，在Mid1和High中间搜索；
2. 如果A[Low] >= A[Mid]，说明Mid落在区间2中，即图中Mid2的位置。同理，如果target小于A[Mid2],那么继续在Low和Mid2中间搜索；否则，在Mid2和High中间搜索。
这样，平均地，我们每次剔除一半数据，时间复杂度是O(logn)。
代码如下：
private static int search2(int[] A, int target){ int lo = 0; int hi = A.length - 1; while(lo <= hi){ int mid = lo + (hi - lo)/2; if(target == A[mid]) return mid; if(A[mid] > A[lo]){ // 他先判断mid和最左边的值 if(target >= A[lo] && target < A[mid]){ hi = mid - 1; }else { lo = mid + 1; } }else { if(target <= A[hi] && target > A[mid]){ lo = mid + 1; }else { hi = mid -1; } } } return -1; }
上述是java的代码。他是先判断A[mid]和最左边的大小，这个时候如果例子是[3,1],要找的target是1，那么就会出现问题。因为先判断左边的时候，此时mid和l下标都是0，且值3大于目标，这时判断A[mid] > A[l]不成立，所以认为要在右边找。但是这是虽然target<=A[hi]成立，但是target>A[mid]不成立，因为此时A[mid]为3大于1.所以执行hi = mid -1;这时就巧妙的错过了正确的答案1.导致输出-1.
考虑到这样的case情况，如果先考虑A[mid]和最右边的大小，就可以通过。
class Solution {public: int search(int A[], int n, int target) { int l = 0, r = n - 1; while(l <= r) { int mid = (l + r)/2; if (A[mid] == target) return mid; if (A[mid] < A[r]) //先考虑和右边的比较 { if (A[mid] < target && A[r] >= target) l = mid + 1; else r = mid - 1; } else { if (A[mid] > target && A[l] <= target) r = mid - 1; else l = mid + 1; } } return -1; }};
如果确实要从左边开始的话也行，那就是利用比值的时候和mid+或者-1的值去比而不是直接和mid比，因为mid已经判断过是不是等于target了。这样也可以避免之前出现的错误。代码如下：
int search(int A[], int n, int target) { int lo = 0; int hi = n - 1; while(lo <= hi){ int mid = lo + (hi - lo)/2; if(target == A[mid]) return mid; if(A[mid] > A[lo]){ if(target >= A[lo] && target <= A[mid-1]){ // mid-1 的话就是小于等于了 hi = mid - 1; }else { lo = mid + 1; } }else { if(target <= A[hi] && target >= A[mid+1]){ lo = mid + 1; }else { hi = mid -1; } } } return -1; }
leetcode第32题--Search in Rotated Sorted Array