Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
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.
Solution 1: if nums[lo]=nums[hi], treat special, other part is same as problem I.
public class Solution {
public boolean search(int[] nums, int target) {
int lo=0, hi=nums.length-1;
while (lo<=hi) {
int mid=lo+(hi-lo)/2;
if (nums[mid]==target) return true;
if (nums[lo]<nums[hi]) {
if (target>nums[mid]) lo=mid+1;
else hi=mid-1;
}
else if (nums[lo]>nums[hi]) {
if (nums[mid]>=nums[lo]) {
if (target<nums[mid] && target>nums[hi]) hi=mid-1;
else lo=mid+1;
}
else {
if (target>nums[mid] && target<nums[lo]) lo=mid+1;
else hi=mid-1;
}
}
else if (target==nums[lo]) return true;
else {
lo++;
hi--;
}
}
return false;
}
}
没有评论:
发表评论