2.练习题

3）

力扣https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/这题需要分三种情况，第一种是区间有序，正常二分查找，第二种是区间 被旋转，左区间的值大于右区间，需要比较目标值和左区间起始值的大小，来判断选择哪一个区间，第三种是无法区分左区间大还是右区间大，此时[left]==[right]，可以直接进行left++或者right--来跳过该值。

代码：

class Solution {
public:bool search(vector<int>& nums, int target) {int left = 0, right = nums.size()-1, mid;while(left<=right){mid = left + (right-left)/2;if(nums[mid]==target) return true;if(nums[left]<nums[right]){if(nums[mid]<target){left = mid + 1;}else{right = mid -1;}}else if(nums[left]>nums[right]){if(target>=nums[left]){   right--;}else{left++;}}else{left++;}}return false;}
};

4)力扣https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/

这题与上一道题类似，也是分析旋转数组可能的情况，找出目标值。

我一开始的思路是继续对数组分类，有序，已旋转，无法区分三类，代码如下：

class Solution {
public:int findMin(vector<int>& nums) {int left = 0, right = nums.size()-1, mid;while(left<right){mid = left + (right-left)/2;if(nums[left]<nums[right]){return nums[left];}if(nums[left]==nums[right]){right--;}else{if(nums[mid]==nums[left]){left++;}else if(nums[mid]>nums[left]){left = mid + 1;}else{left++;right = mid;}}}return nums[left];}
};

可以通过测试，就是代码看起来不够简洁，于是修改了一下，只比较中间值与结束值[right]，代码如下：

class Solution {
public:int findMin(vector<int>& nums) {int left = 0, right = nums.size()-1, mid;while(left<right){mid = left + (right-left)/2;if(nums[mid]==nums[right]){right--;}else if(nums[mid]>nums[right]){left = mid + 1;}else{right = mid;}}return nums[left];}
};

用时确实更短了