The “Search in Rotated Sorted Array II” problem is a classic coding interview question that tests your understanding of binary search and handling duplicates in arrays. In this blog, we\u2019ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.<\/p>\n\n\n\n
There is an integer array Before being passed to your function, Given the array You must decrease the overall operation steps as much as possible.<\/p>\n\n\n\n Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n Example 1:<\/strong><\/p>\n\n\n\n Example 2:<\/strong><\/p>\n\n\n\n Constraints:<\/strong><\/p>\n\n\n\n Follow up:<\/strong> This problem is similar to Search in Rotated Sorted Array<\/a>, but Let\u2019s solve the problem in the most straightforward way:<\/p>\n\n\n\n This approach is easy to understand but not efficient for large arrays.<\/p>\n\n\n\nnums<\/code> sorted in non-decreasing order (not necessarily with distinct<\/strong> values).<\/p>\n\n\n\nnums<\/code> is rotated<\/strong> at an unknown pivot index k<\/code> (0 <= k < nums.length<\/code>) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]<\/code> (0-indexed<\/strong>). For example, [0,1,2,4,4,4,5,6,6,7]<\/code> might be rotated at pivot index 5<\/code> and become [4,5,6,6,7,0,1,2,4,4]<\/code>.<\/p>\n\n\n\nnums<\/code> after<\/strong> the rotation and an integer target<\/code>, return true<\/code> if <\/em>target<\/code> is in <\/em>nums<\/code>, or <\/em>false<\/code> if it is not in <\/em>nums<\/code>.<\/em><\/p>\n\n\n\nInput:<\/strong> nums = [2,5,6,0,0,1,2], target = 0
Output:<\/strong> true<\/pre>\n\n\n\nInput:<\/strong> nums = [2,5,6,0,0,1,2], target = 3
Output:<\/strong> false<\/pre>\n\n\n\n\n
1 <= nums.length <= 5000<\/code><\/li>\n\n\n\n-104<\/sup> <= nums[i] <= 104<\/sup><\/code><\/li>\n\n\n\nnums<\/code> is guaranteed to be rotated at some pivot.<\/li>\n\n\n\n-104<\/sup> <= target <= 104<\/sup><\/code><\/li>\n<\/ul>\n\n\n\nnums<\/code> may contain duplicates<\/strong>. Would this affect the runtime complexity? How and why?<\/p>\n\n\n
\n\n\n\nBrute Force Solution (Linear Search)<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
\n
Go through the array from start to end.<\/li>\n\n\n\n
If any element matches the target, return True<\/code>.<\/li>\n\n\n\n
We check every element, so we won\u2019t miss the target if it\u2019s there.<\/li>\n<\/ol>\n\n\n\nCode Implementation<\/h3>\n\n\n\n