首页 > 代码库 > [leetcode] Search in Rotated Sorted Array II
[leetcode] Search in Rotated Sorted Array II
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.
https://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/
思路：类似Search in Rotated Sorted Array的思路，只不过现在的问题是有重复，可能出现a[l]==a[m]的极端情况，无法判断哪半边有序，因此这种情况下只能一步一步移动l 直到不相等然后通过二分判断。
复杂度：极端情况每次都是减一 而不是减去一半，所以复杂度是O(N)。
/** * http://blog.csdn.net/linhuanmars/article/details/20525681 * * @author jd * */public class Solution { public boolean search(int[] A, int target) { if (A == null || A.length == 0) return false; int l = 0; int r = A.length - 1; while (l <= r) { int m = (l + r) / 2; if (A[m] == target) return true; if (A[m] > A[l]) { if (A[m] > target && A[l] <= target) { r = m - 1; } else { l = m + 1; } } else if (A[m] < A[l]) { if (A[m] < target && A[r] >= target) { l = m + 1; } else { r = m - 1; } } else { l++; } } return false; } public static void main(String[] args) { System.out.println(new Solution().search(new int[] { 3, 1, 1 }, 3)); System.out.println(new Solution().search(new int[] { 2, 3, 3, 3, 3 }, 2)); System.out.println(new Solution().search(new int[] { 3, 2, 3, 3, 3 }, 2)); System.out.println(new Solution().search(new int[] { 3, 3, 3, 2, 3 }, 2)); System.out.println(new Solution().search(new int[] { 3, 3, 3, 3, 2 }, 2)); }}
参考：
http://blog.csdn.net/linhuanmars/article/details/20525681
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。