Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
A:
-----------------------第二遍-------------不管不顾pivot点, 思想跟问题一一样,就是通过看begin 和end两个位置的点的值,如果前者 < 后者, 正常顺序,二分查找。
如果A[begin] >= A[end] 这个区间,含有pivot , 二分查找的,两部分都要查。
最终还是 O(n)
public class Solution { public boolean search(int[] nums, int target) { return search(nums, 0,nums.length-1,target); } private boolean search(int[] A, int begin, int end, int target){ if(begin > end) return false; int mid = (begin+end)/2; if(A[mid]==target)// check this pivot position return true; if(A[begin]<A[end]) return A[mid]>target?search(A,begin,mid-1,target):search(A,mid+1,end,target); else // may need search two sides return search(A,begin,mid-1,target) || search(A,mid+1,end,target); } }
就是把1 的方法copy过来,然后,把所有的return 中的 -1 换成 false, i 换成true。即可------------但思想还是先找到pivot下标。需要遍历,这样是不对的
public class Solution { public boolean search(int[] A, int target) { // assume A is sorted in ascending order if (A.length == 0) return false; int pivotIndex = -1; // find pivot while searching if (A[0] == target) { return true; } 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 false; // not need to continue search } if (A[i] == target) { return true; } else if (A[i] < target) { i++; } else { // A[i] > target return false; // 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 true; } else if (A[i] < target) { i++; } else { // A[i] > target return false; } } } return false; // need when A[0]> target, and all a[i]<target } }
No comments:
Post a Comment