首页 > 代码库 > 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.
class Solution {public: bool search(int A[], int n, int target) { int i = 0; int j = n - 1; while(i <= j){ int mid = (i + j) / 2; if(A[mid] == target) return true; else if(A[mid] < A[i]){ if(target > A[j]) j = mid - 1; else if(target < A[mid]) j = mid - 1; else i = mid + 1; }else if(A[mid] > A[i]){ if(target < A[mid] && target >= A[i]) j = mid - 1; else i = mid + 1; }else{ // A[mid] == A[i] if(A[mid] != A[j]) i = mid + 1; else{ bool flag = true; for(int k = 1; mid - k >= i && mid + k <= j; k++){ if(A[mid] != A[mid - k]){ j = mid - k; flag = false; break; }else if(A[mid] != A[mid + k]){ i = mid + k; flag = false; break; } } if(flag) return false; } } } return false; }};
Search in Rotated Sorted Array II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。