[LeetCode95]Search in Rotated Sorted Array II

本文主要是介绍[LeetCode95]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.

Analysis:

重复元素的确会影响A[m]>=A[l] 判断递增序列，比如[1,4,5,1,1,1,1]

如果A[m]>=A[l]不能确定递增，那就把它拆分成两个条件
1. A[m]>A[l] 递增
2. A[m] ==A[l] 确定不了，那就l++，往下看一步即可。

Java

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[l]<=target && A[m]>target){r = m-1;}elsel = m+1;}else if(A[m]<A[l]){if(A[m]<target && target<=A[r])l = m+1;elser = m-1;}else {l++;}}return false;

c++

bool search(int A[], int n, int target) {int start = 0;int end = n-1;while(start <= end){int mid = (start + end)/2;if(A[mid] == target) return true;if(A[mid] > A[start]){if(target <= A[mid] && target >= A[start]) end = mid-1;else start = mid+1;}else if(A[mid]< A[start]){if(target >= A[start] || target < A[mid]) end = mid-1;else start = mid+1;}else{start++;}}return false;}

这篇关于[LeetCode95]Search in Rotated Sorted Array II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---