Description

LeetCode 33

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1

LeetCode 81

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

• 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?

Analysis

The first problem asks us to implement a $$O(logn)$$ method. So it is easy to come up with binary search. In a general binary search, we could judge the position of target by comparing it with the middle element. However, it does not work for the rotated array.

So how can we judge the position? Is the target on the left or right? We know in the rotated sorted array, just one position is not sorted. So this position must be in either left or right to the middle element, that is to say, one of the side of the middle element must be sorted. A sorted subarray could be checked by comparing the first element and the last element. And we could compare the target with the first element and the last element to judge if it is in the subarray. Therefore, we could judge if one side is a sorted array and if the target is in this side. This process could work iteratively to find the target.

The time is $$O(logn)$$ and the space is $$O(1)$$.

However, the second problem concentrates on the cases that has duplicate elements. Is the similar to the first problem? In the first problem’s binary search method, an important step is to compare the first element with the middle element and the middle element with the last element. So what if the three elements are all the same? We could not judge which part is sorted. We can just throw the first element and the last element out and search the array left. For example, search $$0$$ in $${2, 2, 2, 2, 2, 2, 2, 2, 0, 2}$$.

Therefore, we could only ensure that the average time is $$O(logn)$$. But the worst time is $$O(n)$$. The worst time is same as brute-force search.

Solution

//LeetCode 33
class Solution {
public int search(int[] nums, int target) {
if(nums.length==0) return -1;
int low=0,high=nums.length-1;
while(low<=high)
{
int mid=(high-low)/2+low;
if(target==nums[mid]) return mid;
if(nums[low]<=nums[mid])
{
if(target>=nums[low]&&target<=nums[mid])
{
high=mid-1;
}
else
{
low=mid+1;
}
}
else
{
if(target>=nums[mid]&&target<=nums[high])
{
low=mid+1;
}
else
{
high=mid-1;
}
}
}
return -1;
}
}

//LeetCode 81
class Solution {
public boolean search(int[] nums, int target) {
if(nums.length==0) return false;
int low=0,high=nums.length-1;
while(low<=high)
{
int mid=(high-low)/2+low;
if(target==nums[mid]) return true;
if(nums[low]==nums[mid]&&nums[mid]==nums[high])
{
low++;
high--;
}
else if(nums[low]<=nums[mid])
{
if(target>=nums[low]&&target<=nums[mid])
{
high=mid-1;
}
else
{
low=mid+1;
}
}
else
{
if(target>=nums[mid]&&target<=nums[high])
{
low=mid+1;
}
else
{
high=mid-1;
}
}
}
return false;
}
}