Search in Rotated Sorted Array II

xiaoxiao2021-03-01  9

题目描述:

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

现在,假设数组中的元素不会重复。 (1)当mid < < <script type="math/tex" id="MathJax-Element-159"><</script>right 的元素的时候,如果mid < < <script type="math/tex" id="MathJax-Element-160"><</script>target right中的元素的时候,可以得知元素在[mid,right]范围内,因此可以在这个区间内查找target。否则说明target在另一侧,令right = mid-1即可。 (2)当mid>left的时候,如果left target < < <script type="math/tex" id="MathJax-Element-163"><</script>mid的时候,可以得知元素在[left,mid]中,可以在此范围中查找。否则说明在另一半范围中,此时令left = mid+1。 (3)当mid==target的时候,返回true。

这道题目和之前的Search in Rotated Sorted Array的区别在于,本题目中数组元素可以重复。这样就增加了寻找难度。具体体现在,假设现在有旋转后的数组nums = {2,0,2,2,2},这时候left、mid和right的元素相同,无法判断应该跳向哪一侧。此时较好的办法时,将left+1,将right-1,继续缩小查找范围。

值得说明的是,上述代码也适用于没有重复元素的rotated Array中target的查找。

class Solution { public: bool search(vector<int>& nums, int target) { int left = 0, right = nums.size()-1, mid; while(left<=right) { mid = (left + right) >> 1; if(nums[mid] == target) return true; // the only difference from the first one, trickly case, just updat left and right if( (nums[left] == nums[mid]) && (nums[right] == nums[mid]) ) {++left; --right;} else if(nums[left] <= nums[mid]) { if( (nums[left]<=target) && (nums[mid] > target) ) right = mid-1; else left = mid + 1; } else { if((nums[mid] < target) && (nums[right] >= target) ) left = mid+1; else right = mid-1; } } return false; } };
转载请注明原文地址: https://www.6miu.com/read-3350160.html

最新回复(0)