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.
A: 目标是找到pivot,并通过线性查找,来找到pivot,然后,才进行正常的二分查找。 这样的复杂度为O(n)
public class Solution { public int search(int[] A, int target) { // assume A is sorted in ascending order if (A.length == 0) return -1; int pivotIndex = -1; // find pivot while searching if (A[0] == target) { return 0; } if (A[0] < target) { // search the first half part int i = 1; while (i < A.length) { if (A[i] < A[i - 1]) { // i+1 is the pivot, // pivotIndex = i; return -1; // not need to continue search } if (A[i] == target) { return i; } else if (A[i] < target) { i++; } else { // A[i] > target return -1; // do not exist in A } } } else { // A[0] > target , ----> search the left half part // find pivot , because the first rotated part are all > // target int i = 1; while (i < A.length) { if (A[i] < A[i - 1]) { pivotIndex = i; break; } else { i++; } } // search from pivotIndex; i = Math.max(0,pivotIndex); while (i < A.length) { if (A[i] == target) { return i; } else if (A[i] < target) { i++; } else { // A[i] > target return -1; } } } return -1; // if A[0] > target , and // all values are smaller than target. run this } }
Mistakes:
1: 当 A[0] > target 的情况时, 没有考虑找不到pivot 的情况。例如,数组 只有一个值
-------------------第二遍-----------
思想: 对每一个区间 begin 到end .通过对比首尾的值,来确定,是否该区间包含了pivot。
如果不是,则对比A[mid], 来确定是接下来对比左边,还是右边。
如果A[begin]>= A[end]则包含了pivot节点。我们把两边都查找,并归并结果。
public class Solution { public int search(int[] A, int target) { return search(A,0,A.length-1,target); } private int search(int[] A, int begin, int end, int target){ if(begin>end){ return -1; } if(begin == end){ if(A[begin]==target){ return begin; }else{ return -1; } } // test whether this section is rotated int mid = (begin+end)/2; if(A[begin]<A[end]){ // search only one part int left=-1 ,right=-1;// must be clearlly initiallized if(A[mid] >=target){ // on left part left = search(A,begin,mid,target); }else{ // target lies on right part right = search(A,mid+1,end,target); } return Math.max(left,right); }else{ // search both part int left = search(A,begin,mid,target); int right = search(A,mid+1,end,target); return Math.max(left,right); } } }---------Mistakes:
1: for the first case of left and right value, it must be clearly initialzied, we cannot assume their default value.
------------------3rd search both both part directly ------------------------
public class Solution { public int search(int[] A, int target) { return search2(A,0,A.length -1, target); } private int search2(int[] A, int start, int end, int target){ if(start>end) return -1; int mid = (start+end)/2; if( A[mid] == target ) return mid; int result = -1; if(A[start] >= A[mid] || A[mid]>target) result = search2(A,start,mid-1,target); if(result == -1 &&( A[mid] >= A[end] || A[mid] < target )) result = search2(A,mid+1,end,target); return result; } }
No comments:
Post a Comment