Search in Rotated Sorted Array
Before we search for a specific number, let's try to find the min of a rotated sorted array.
Find Minimum in Rotated Sorted Array (LC.153)
Find the minimum of a rotated sorted array.
You may assume no duplicate exists in the array.
Example
A RSA is a sorted array that is rotated at some pivot
[0 1 2 4 5 6 7] might become [4 5 6 7 0 1 2]
Return: 0
Analysis
The array is almost sorted. We can definitely do a binary search with some slight modifications. We can take either staring at an example for an hour or just take and analyze this smart insight - pick the last element as the target and find the first index where A[index] <= target. Essentially, we need to convert this question back to the [T, T, T, F, F] vanilla binary search problem. In a way, if you noticed, this question is really first bad version in disguise.
Code
public int findMin(int[] nums) {
if (nums == null || nums.length == 0)
return -1;
int target = nums[0];
int start = 0, mid, end = nums.length - 1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (nums[mid] <= target) {
// the median less than target, search left
end = mid;
} else {
// when the median > target, search right
// so if we set the first ele as our target, we will skip it here
start = mid + 1;
}
}
// base case
if (nums[start] < nums[end]) {
return nums[start];
} else {
return nums[end];
}
}
Ok. Why the heck that we picked the last element as our target instead of the first element? [1, 2, 3, 4, 5] trace the code with this example. The code will have to search right when it needs to search left. Selecting the last element will avoid this problem.
Follow Up (LC.154)
Now we need to consider the case where the input array might contain duplicates.
Example
Input: [0, 1, 3, 3, 3] not an issue
cause 3 is the pivot, end = mid, we search the left half [0,1,3]
How about
Input: [3, 3, 0, 1, 3] still fine we will return 0
But
Input: [3, 3, 1, 3] this is problematic
The pivot is 3. so end = mid (at index 1)
The end pointer will point to the second 3 and never get to 1 ʕ ·㉨·ʔ
Setting end = mid, when the first position of <= last element won't work anymore. We need to analyze what happens when A[mid] == target and figure out what else to do.
Analysis
What happens when A[mid] == target? Because of the duplicates we cannot dump the right half of the array. There is a chance that the minimum is on the right side. Instead of dumping the right subarray, we will only dump the duplicate element. Therefore, in the beginning of the each loop, we need to pick a new pivot (the old one might get dumped).
Code
public int findMin(int[] nums) {
if (nums == null || nums.length == 0)
return -1;
int target;
int start = 0, mid, end = nums.length - 1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
target = nums[end];
if (nums[mid] == target) {
// the median equal to the target, skip duplicates here
// might be linear time
end--;
} else if (nums[mid] < target) {
// the median less than target, search left
end = mid;
} else {
// when the median > target, search right
start = mid + 1;
}
}
// base case
if (nums[start] < nums[end]) {
return nums[start];
} else {
return nums[end];
}
}
Time Complexity
Since we cannot guarantee to throw away half of the phone book at each check (we can only tear the last page when A[mid] == pivot), the worst case will no longer be the prestigious O(logn). A worst case like [3, 3, 3, 3] will have O(n) runtime. Although duplicates have brought down the worst case down to O(n), the average case remains O(logn) (we assume the likelihood of duplicates is small).
Reflection on Follow Up
Keep doing examples until find one that breaks the current code. And figure out why it breaks the current code. Then modify the code so that it keeps the current functionality while handles the new cases properly.
Search in Rotated Sorted Array (LC.33)
Given a RSA and a target, find the index of the target in the RSA. If the target does not exist, return -1.
You may assume no duplicate exists in the array.
Example
Input: nums = [4, 5, 1, 2, 3], target = 1
Return: index 2
Input: nums = [4, 5, 1, 2, 3], target = 0
Return: doesn't exist -1
Analysis
Well we can first find the minimum in O(logn) then we binary search the target in that range O(logn). Interviewer: Yep, this works. But can you do in one binary search? Interviewee: ^@#%bbg^@%#&3jynern ʕ ᵒ̌ ‸ ᵒ̌ ʔ
Alright, so to do one binary search we need a condition that allows us to dump half of the array each check.
Analyzing Code
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0, mid, end = nums.length - 1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
} else if (target >= nums[start] && target < nums[mid]) {
// mid cut #1 in the left side of the rotating pivot
// we can dump the right half cause target < nums[mid]
end = mid - 1;
} else if (target > nums[mid] && target <= nums[end]){
// mid cut #2 is in the right side of the rotating pivot
// dump the left half cause we know target > nums[mid]
start = mid + 1;
} else {
if (nums[start] < nums[mid]) {
// mid cut #1 but we need to dump the left half
start = mid + 1;
} else {
// mid cut #2 we need to dump the right half
end = mid - 1;
}
}
}
if (nums[start] == target) {
return start;
} else if (nums[end] == target) {
return end;
} else {
return -1;
}
}
Why this approach does not work?
// mid cut #1 but we need to dump the left half
if (target > nums[mid] && target >= nums[end]) {
start = mid + 1;
} else if (target < nums[mid] && target <= nums[start]) {
// mid cut #2 we need to dump the right half
end = mid - 1;
}
This is fundamentally wrong because the region identified correctly, but the which half you plan to throw? To fix it, we have to specify which half to throw.
// in the upper region
if (target > nums[mid] && target >= nums[end]) {
if (nums[mid] > nums[start]) {
// mid cut #1 but we need to dump the left half
start = mid + 1;
} else {
// mid cut #2 we need to dump the right half
end = mid - 1;
}
// in the lower region
} else if (target < nums[mid] && target <= nums[start]) {
if (nums[mid] > nums[start]) {
// mid cut #1 but we need to dump the left half
start = mid + 1;
} else {
// mid cut #2 we need to dump the right half
end = mid - 1;
}
}
Solution
- Check where was mid cut (on the left side or the right side)
- mid cut on the left side
- if A[start] <= target < A[mid]
- dump right half
- else
- dump left half
- if A[start] <= target < A[mid]
- mid cut on the right side
- if A[mid] < target <= A[end]
- dump left half
- else
- dump right half
- if A[mid] < target <= A[end]
- mid cut on the left side
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0, mid, end = nums.length - 1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
}
// determine the mid cut was made on the left or right side of the rotating pivot
if (nums[start] < nums[mid]) {
// on the left side
if (target >= nums[start] && target < nums[mid]) {
end = mid - 1; // dump right
} else {
start = mid + 1; // dump left
}
} else {
// on the right side
if (target > nums[mid] && target <= nums[end]) {
start = mid + 1; // dump left
} else {
end = mid - 1; // dump right
}
}
}
if (nums[start] == target) {
return start;
} else if (nums[end] == target) {
return end;
} else {
return -1;
}
}
Follow Up (LC.81)
Search in a RSA. But the input array might have duplicates.
Examples
Again, we try a bunch of examples and figure out why the old code does not work.
Input: nums = [4,5,6,1,2,2,3], target = 3
Ok the code works. How about
Input: nums = [1,1,3,1], target = 3
It failed but why?
Analysis
Analyze what happens when A[start] == A[mid]. We have to skip the duplicates.
Code
// determine where the mid cut was made
if (nums[start] < nums[mid]) {
// on the left side
if (target >= nums[start] && target < nums[mid]) {
end = mid - 1; // dump right
} else {
start = mid + 1; // dump left
}
} else if (nums[start] > nums[mid]){
// on the right side
if (target > nums[mid] && target <= nums[end]) {
start = mid + 1; // dump left
} else {
end = mid - 1; // dump right
}
} else {
// mid is a duplicate need to skip it
start++;
}
Time Complexity
Again, duplicates bring the wrong case down to O(n).