Leetcode 81. Search in Rotated Sorted Array II
Problem Explanation
In this problem, you are given a "rotated" array. This means, an array is initially sorted in ascending order, then some elements from its beginning are taken out and appended at the end which rotates the array. This rotation could occur at any unknown pivot in the array. You are also given a target number, and you have to determine if the target number is present in the array or not. If it is, you return 'True', and if it isn't, you return 'False'.
This might sound a little bit complex, but it isn't. Consider an array: 2,5,6,0,0,1,2. This is the result of rotating the array: 0,0,1,2,2,5,6. As you can see, the elements have just shifted.
The question is designed as a follow-up problem to Search in a Rotated Sorted Array. Here, the difference is that the array may contain duplicate elements.
A key point to consider is that the presence of duplicates can indeed affect the run-time complexity. With duplicates, in the worst case, we might need to examine each element of the array once, therefore having a run-time complexity of O(n).
Example
Consider this rotated array: [2,5,6,0,0,1,2] and our target is 0. As we traverse through the array, we see that 0 is present. Hence, we return True. But if our target is 3, traversing gets us nowhere since 3 is not present in the array. So, we return False.
Solution Approach
Start at the two ends of the array, i.e., at positions l=0 and r=n-1. While l <= r, keep getting the middle element. If the middle element matches the target value, return True.
If the left, middle, and right element all have the same value, we can't really decide which half to go to, so we increment left and decrement right.
If the left half is sorted (i.e., the leftmost element is smaller than or equal to the middle element), we check whether the target lies in this range. If yes, the target must lie on the left half, thus updating right to m - 1. Otherwise, it must lie on the right half, thus updating left to m + 1.
If the right half is sorted (i.e., the middle element is smaller than the rightmost element), we check whether the target lies in this range. If so, update left to m + 1. Otherwise, update right to m - 1.
If we come out of the loop, that means the target value is not present in the array. Return False.
Here are the solutions in various languages. Remember to replace 'Solution' with the class name used in your code.
Python Solution
1 2python 3class Solution: 4 def search(self, nums: List[int], target: int) -> bool: 5 l, r = 0, len(nums) - 1 6 while l <= r: 7 m = (l + r) // 2 8 if nums[m] == target: 9 return True 10 while l < m and nums[l] == nums[m]: # tricky part 11 l += 1 12 if nums[l] <= nums[m]: 13 if nums[l] <= target < nums[m]: 14 r = m - 1 15 else: 16 l = m + 1 17 else: 18 if nums[m] < target <= nums[r]: 19 l = m + 1 20 else: 21 r = m - 1 22 return False
Java Solution
1 2java 3 4public class Solution { 5 public boolean search(int[] nums, int target) { 6 int l = 0, r = nums.length - 1; 7 while (l <= r) { 8 int m = (l + r) / 2; 9 if (nums[m] == target) return true; 10 if (nums[l] == nums[m] && nums[r] == nums[m]) { l++; r--; } 11 else if (nums[l] <= nums[m]) { 12 if (target >= nums[l] && target < nums[m]) r = m - 1; 13 else l = m + 1; 14 } else { 15 if (target > nums[m] && target <= nums[r]) l = m + 1; 16 else r = m - 1; 17 } 18 } 19 return false; 20 } 21} 22
JavaScript Solution
1 2JavaScript 3var search = function(nums, target) { 4 let low = 0, high = nums.length - 1; 5 6 while (low <= high) { 7 let mid = Math.floor((low + high) / 2); 8 9 if (nums[mid] === target) return true; 10 11 while (nums[low] === nums[mid] && low !== mid) low++; 12 13 if (nums[low] <= nums[mid]) { 14 if (nums[low] <= target && target < nums[mid]) high = mid - 1; 15 else low = mid + 1; 16 } else { 17 if (nums[mid] < target && target <= nums[high]) low = mid + 1; 18 else high = mid - 1; 19 } 20 } 21 22 return false; 23}; 24
C++ Solution
1 2cpp 3class Solution { 4public: 5 bool search(vector<int>& nums, int target) { 6 int l = 0; 7 int r = nums.size() - 1; 8 9 while (l <= r) { 10 int m = (l + r) / 2; 11 if (nums[m] == target) 12 return true; 13 if (nums[l] == nums[m] && nums[m] == nums[r]) { 14 ++l; 15 --r; 16 } else if (nums[l] <= nums[m]) { 17 if (nums[l] <= target && target < nums[m]) 18 r = m - 1; 19 else 20 l = m + 1; 21 } else { 22 if (nums[m] < target && target <= nums[r]) 23 l = m + 1; 24 else 25 r = m - 1; 26 } 27 } 28 29 return false; 30 } 31};
C# Solution
1 2Csharp 3 4public class Solution { 5 public bool Search(int[] nums, int target) { 6 int l = 0, r = nums.Length - 1; 7 while (l <= r) 8 { 9 int mid = l + (r-1)/2; 10 if (nums[mid] == target) return true; 11 12 // the only difference from the first one, trickly handle nums[start] == nums[mid] 13 if (nums[l] == nums[mid] && nums[r] == nums[mid]) {++l; --r;} 14 15 else if (nums[l] <= nums[mid]) 16 { 17 if (nums[l] <= target && target < nums[mid]) r = mid - 1; 18 else l = mid + 1; 19 } 20 else 21 { 22 if (nums[mid] < target && target <= nums[r]) l = mid + 1; 23 else r = mid - 1; 24 } 25 } 26 return false; 27 } 28} 29
Swift Solution
1
2swift
3class Solution {
4 func search(_ nums: [Int], _ target: Int) -> Bool {
5 var left = 0
6 var right = nums.count - 1
7
8 while left <= right {
9 let mid = (left + right) / 2
10 if nums[mid] == target {
11 return true
12 }
13
14 if nums[left] == nums[mid] && nums[mid] == nums[right] {
15 left += 1
16 right -= 1
17 } else if nums[left] <= nums[mid] {
18 if target >= nums[left] && target < nums[mid] {
19 right = mid - 1
20 } else {
21 left = mid + 1
22 }
23 } else {
24 if target > nums[mid] && target <= nums[right] {
25 left = mid + 1
26 } else {
27 right = mid - 1
28 }
29 }
30 }
31
32 return false
33 }
34}
First, we create a class Solution
with a function search
that takes in the array nums
and the target integer value.
In the method, we declare two pointers left
and right
, representing the left and right ends of the array. While left
is less than or equal to right
, we get the middle element of the array. If this element matches the target, we return True
.
Next, we handle the tricky case where left, middle, and right elements are all the same. In this case, we can't determine which half to explore, so we increment left
and decrement right
.
Then, we check if the left half is sorted (i.e., the leftmost element is less than or equal to the middle one). If the target lies within this range, we know it's in the left half, so we update right
to mid - 1
. If not, it must be in the right half, so we update left
to mid + 1
.
If the right half is sorted (i.e., the middle element is less than the rightmost one), we check if the target is in this range. If so, we update left
to mid + 1
, otherwise, we update right
to mid - 1
.
Finally, if the target was not found in this process, we return False
. This completes the method and allows us to determine if the target is present in the array or not.
This solution is efficient with a time complexity of O(log n) in the best case scenario when there are no duplicates and O(n) in the worst case when duplicates are present.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.