Description:
There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).
Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].
Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.
You must decrease the overall operation steps as much as possible.
Examples:
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: falseSolution in Python:
To solve the problem of searching for a target value in a rotated sorted array that may contain duplicates, we can use a modified version of binary search. The challenge here is to handle the cases where duplicates exist, which can make it harder to determine the sorted half of the array.
Python
from typing import List
class Solution:
def search(self, nums: List[int], target: int) -> bool:
# Initialize the left and right pointers for binary search
left, right = 0, len(nums) - 1
# Binary search loop
while left <= right:
# Calculate the middle index
mid = (left + right) // 2
# Check if the target is found at the middle index
if nums[mid] == target:
return True
# When there are duplicates, it can be hard to decide which part is sorted.
# We need to handle duplicates by shrinking the search space
if nums[left] == nums[mid] == nums[right]:
left += 1
right -= 1
# If the left half is sorted
elif nums[left] <= nums[mid]:
# Check if the target lies within the sorted left half
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# If the right half is sorted
else:
# Check if the target lies within the sorted right half
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
# If the loop completes without returning, the target is not in the array
return FalseExplanation:
- Initialize Pointers:
leftandrightare initialized to the start and end of the array, respectively.
- Binary Search Loop:
- The loop continues as long as
leftis less than or equal toright.
- The loop continues as long as
- Calculate Middle Index:
mid = (left + right) // 2: Compute the middle index.
- Check Middle Element:
- If
nums[mid]equals the target, returnTrue.
- If
- Handling Duplicates:
- If
nums[left] == nums[mid] == nums[right], it’s hard to decide the sorted part, so we shrink the search space by incrementingleftand decrementingright.
- If
- Determine Sorted Half:
- If the left part is sorted (
nums[left] <= nums[mid]):- Check if the target is within this sorted left half (
nums[left] <= target < nums[mid]). - Adjust
rightif the target is in the left half; otherwise, adjustleft.
- Check if the target is within this sorted left half (
- If the right part is sorted:
- Check if the target is within this sorted right half (
nums[mid] < target <= nums[right]). - Adjust
leftif the target is in the right half; otherwise, adjustright.
- Check if the target is within this sorted right half (
- If the left part is sorted (
- Return Result:
- If the loop exits without finding the target, return
False.
- If the loop exits without finding the target, return
This approach ensures we handle the rotated sorted array with potential duplicates efficiently using binary search while adjusting for cases where the sorted part is not easily identifiable due to duplicates.
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @param {number} target
* @return {boolean}
*/
var search = function(nums, target) {
// Initialize the left and right pointers for binary search
let left = 0;
let right = nums.length - 1;
// Binary search loop
while (left <= right) {
// Calculate the middle index
let mid = Math.floor((left + right) / 2);
// Check if the target is found at the middle index
if (nums[mid] === target) {
return true;
}
// When there are duplicates, it can be hard to decide which part is sorted.
// We need to handle duplicates by shrinking the search space
if (nums[left] === nums[mid] && nums[mid] === nums[right]) {
left++;
right--;
}
// If the left half is sorted
else if (nums[left] <= nums[mid]) {
// Check if the target lies within the sorted left half
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// If the right half is sorted
else {
// Check if the target lies within the sorted right half
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
// If the loop completes without returning, the target is not in the array
return false;
};Solution in Java:
Java
class Solution {
public boolean search(int[] nums, int target) {
// Initialize the left and right pointers for binary search
int left = 0;
int right = nums.length - 1;
// Binary search loop
while (left <= right) {
// Calculate the middle index
int mid = left + (right - left) / 2;
// Check if the target is found at the middle index
if (nums[mid] == target) {
return true;
}
// When there are duplicates, it can be hard to decide which part is sorted.
// We need to handle duplicates by shrinking the search space
if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
left++;
right--;
}
// If the left half is sorted
else if (nums[left] <= nums[mid]) {
// Check if the target lies within the sorted left half
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// If the right half is sorted
else {
// Check if the target lies within the sorted right half
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
// If the loop completes without returning, the target is not in the array
return false;
}
}Solution in C#:
C#
public class Solution {
public bool Search(int[] nums, int target) {
// Initialize the left and right pointers for binary search
int left = 0;
int right = nums.Length - 1;
// Binary search loop
while (left <= right) {
// Calculate the middle index
int mid = left + (right - left) / 2;
// Check if the target is found at the middle index
if (nums[mid] == target) {
return true;
}
// When there are duplicates, it can be hard to decide which part is sorted.
// We need to handle duplicates by shrinking the search space
if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
left++;
right--;
}
// If the left half is sorted
else if (nums[left] <= nums[mid]) {
// Check if the target lies within the sorted left half
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// If the right half is sorted
else {
// Check if the target lies within the sorted right half
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
// If the loop completes without returning, the target is not in the array
return false;
}
}