Search in Rotated Sorted Array II

/* Description: Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array Follow up for ”Search in Rotated Sorted Array”: What if duplicates are allowed? Would this affect the run-time complexity? How and why? Write a function to determine if a given target is in the array */ /* Parse:二分查找，难度主要在于左右边界的确定。 假设有一个排序的按未知的旋转轴旋转的数组(比如，0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。 给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。 给出[4, 5, 1, 2, 3]和target=1，返回 2 给出[4, 5, 1, 2, 3]和target=0，返回 -1 note:没有重复的元素是重要信息 允许重复元素，则上一题中如果A[m]>=A[l],那么，[l,m]为递增序列的假设就不能成立了，比如[1,3,1,1,1]。 如果A[m]>=A[l]不能确定递增，那就把它拆分成两个条件: -若A[m]>=A[l]，则区间[l,m]一定递增 -若A[m]==A[l]确定不了，那就l++,往下看一步即可。 */ // LeetCode, Search in Rotated Sorted Array II // 时间复杂度 O(n)空间复杂度(1) #include<iostream> #include<vector> using namespace std; class Solution { public: bool search(const vector<int>& nums, int target) { int first = 0, last = nums.size(); while (first != last) { const int mid = first + (last - first) / 2; if (nums[mid] == target) { return true; } if (nums[first] < nums[mid]) { if (nums[first] <= target && target < nums[mid]) { last = mid; } else { first = mid + 1; } } else if (nums[first] > nums[mid]) { if (nums[mid] < target && target <= nums[last-1]) { first = mid + 1; } else { last = mid; } } else { //skip duplicate one first++; } } return false; } }; int main(){ Solution a; vector<int> nums; nums.push_back(0); nums.push_back(1); nums.push_back(2); nums.push_back(4); nums.push_back(5); nums.push_back(5); nums.push_back(6); nums.push_back(7); int b=a.search(nums,1); cout<<b; return 0; }