This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
Would this affect the run-time complexity? How and why?
Solutions:
class Solution {
public boolean search(int[] nums, int target) {
// note here end is initialized to len instead of (len-1)
int start = 0, end = nums.length;
while (start < end) {
int mid = (start + end) / 2;
if (nums[mid] == target) return true;
if (nums[mid] > nums[start]) { // nums[start..mid] is sorted
// check if target in left half
if (target < nums[mid] && target >= nums[start]) end = mid;
else start = mid + 1;
} else if (nums[mid] < nums[start]) { // nums[mid..end] is sorted
// check if target in right half
if (target > nums[mid] && target < nums[start]) start = mid + 1;
else end = mid;
} else { // have no idea about the array, but we can exclude nums[start] because nums[start] == nums[mid]
start++;
}
}
return false;
}
}
Points:
With low, mid, high pointers, we should check the value of mid with the two borders and tell whether the left or right part of the array is sorted or not.
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0 Output: true Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3 Output: false Follow up:
This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates. Would this affect the run-time complexity? How and why?
Solutions: class Solution { public boolean search(int[] nums, int target) { // note here end is initialized to len instead of (len-1) int start = 0, end = nums.length; while (start < end) { int mid = (start + end) / 2; if (nums[mid] == target) return true; if (nums[mid] > nums[start]) { // nums[start..mid] is sorted // check if target in left half if (target < nums[mid] && target >= nums[start]) end = mid; else start = mid + 1; } else if (nums[mid] < nums[start]) { // nums[mid..end] is sorted // check if target in right half if (target > nums[mid] && target < nums[start]) start = mid + 1; else end = mid; } else { // have no idea about the array, but we can exclude nums[start] because nums[start] == nums[mid] start++; } } return false; } }
Points: