首页 > 代码库 > Search in Rotated Sorted Array II
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.
思路：与“Search in Rotated Sorted Array”类似。只需增加考虑A[start]==A[end]的情况即可，因为此时存在不确定的情况：A[middle]==A[start]，此时，我们无法确定A[middle]是来自第一个序列还是第二个序列。
1 class Solution { 2 public: 3 bool search( int A[], int n, int target ) { 4 int start = 0, end = n-1; 5 while( start <= end ) { 6 int middle = ( start + end ) / 2; 7 if( A[middle] == target || A[start] == target || A[end] == target ) { return true; } 8 if( A[start] < A[end] ) { 9 if( A[middle] < target ) {10 start = middle + 1;11 --end;12 } else {13 end = middle - 1;14 ++start;15 }16 } else if( A[start] > A[end] ){17 if( A[middle] < target ) {18 if( target > A[start] && A[middle] < A[start] ) {19 end = middle - 1;20 ++start;21 } else {22 start = middle + 1;23 --end;24 }25 } else {26 if( target < A[start] && A[middle] >= A[start] ) {27 start = middle + 1;28 --end;29 } else {30 end = middle - 1;31 ++start;32 }33 }34 } else {35 ++start; --end;36 }37 }38 return false;39 }40 };
Search in Rotated Sorted Array II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。