首页 > 代码库 > 【LeetCode】Search in Rotated Sorted Array II (2 solutions)
【LeetCode】Search in Rotated Sorted Array II (2 solutions)
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) { for(int i = 0; i < n; i ++) { if(A[i] == target) return true; } return false; }};
解法二：二分查找
关键点在于，如果mid元素与low或者high元素相同，则删除一个low或者high
class Solution {public: bool search(int A[], int n, int target) { int low = 0; int high = n-1; while (low <= high) { int mid = (low+high)/2; if(A[mid] == target) return true; if (A[low] < A[mid]) { if(A[low] <= target && target < A[mid]) //binary search in sorted A[low~mid-1] high = mid - 1; else //subproblem from low to high low = mid + 1; } else if(A[mid] < A[high]) { if(A[mid] < target && target <= A[high]) //binary search in sorted A[mid+1~high] low = mid + 1; else //subproblem from low to mid-1 high = mid - 1; } else if(A[low] == A[mid]) low += 1; //A[low]==A[mid] is not the target, so remove it else if(A[mid] == A[high]) high -= 1; //A[high]==A[mid] is not the target, so remove it } return false; }};
【LeetCode】Search in Rotated Sorted Array II (2 solutions)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。