1.旋转数组的最小数字

把一个数组最开始的若干元素搬到数组的末尾称为数组的旋转。旋转后的数组由两个有序数组构成，中间是分界点。此题和下一道题的一个区别是：数组中可以有重复的数字。比如4 3 4 4 4

二分查找：开始时，先找出有序集合中间的那个元素。如果此元素比要查找的元素大，就接着在较小的一个半区进行查找；反之，如果此元素比要找的元素小，就在较大的一个半区进行查找。在每个更小的数据集中重复这个查找过程，直到找到要查找的元素或者数据集不能再分割。在二分搜索中，我们找到区间的中间点并根据某些条件决定去区间左半部分还是右半部分搜索。下面是二分查找的递归实现：

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

方法一：暴力法

class Solution {
public:int minArray(vector<int>& numbers) {if(numbers.size()==1) return numbers[0];
for(int i=0;i<numbers.size()-1;i++){if(numbers[i]>numbers[i+1]) return numbers[i+1];
}
return numbers[0];}
};

方法二：二分法

参考的官方的视频题解。一个题目能使用二分法需要满足两个条件：①根据下标可以找到关键字②根据比较结果可以判断下一步的搜索范围。为什么left=mid+1而right=mid?前一种情况中可以确定nums[mid]不是要找的最小的值了，后一种情况中nums[mid]还有可能是我们要找的最小值。为什么相等的时候right--?nums[right]不是我们要找的最小值了，相当于暴力搜索中的挪一位。

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

2.寻找旋转排序数组中的最小值

本题中可以假设数组中的元素没有重复的。怎么判断一个有序数组有没有被旋转过？数组的最后一个元素小于第一个元素则有序数组被旋转过。问题中存在一个变化点，如何搜索这个变化点呢？变化点的特点有：左侧元素大于数组第一个元素，右侧元素小于数组第一个元素。

class Solution {
public:int findMin(vector<int>& nums) {
if(nums.size()==0) return -1;
if(nums.size()==1) return nums[0];
int left=0, right=nums.size()-1;
if(nums[0]<nums[right]) return nums[0];//这一行一定是要有的，确保下面的都是旋转了的数组
while(left<=right){int mid=left+(right-left)/2;if(nums[mid]>nums[mid+1]) return nums[mid+1];if(nums[mid]<nums[mid-1]) return nums[mid];if(nums[mid]>nums[0]) {left=mid+1;}//if(nums[mid]>nums[right]) {left=mid+1;}也可以这么写，说明分界点就在mid和right之间else {right=mid-1;}
}
return -1;}
};

3.在排序数组中查找数字 

此题的相关标签是数组，二分查找。统计一个数字在排序数组中出现的次数。需要记住这个算法,怎么来寻找左右边界。

class Solution {
public:int search(vector<int>& nums, int target) {if(nums.size()==0) return 0;if(nums.size()==1&&nums[0]!=target) return 0;
int i=0,j=nums.size()-1;
while(i<=j){//寻找右边界int mid=(i+j)/2;if(nums[mid]>target){j=mid-1;}else if(nums[mid]<target){i=mid+1;}else{i=mid+1;}
}
int right=i;
if(j>=0&&nums[j]!=target) return 0;//这一行非常重要，j现在应该指向的是最后一个target（如果存在的话）
i=0;
while(i<=j){//寻找左边界int mid=(i+j)/2;if(nums[mid]>target){j=mid-1;}else if(nums[mid]<target){i=mid+1;}else{j=mid-1;}
}
int left=j;
cout<<right<<" "<<left;
return right-left-1;}};

4.在排序数组中查找元素的第一个和最后一个位置

注意[2 2] 1这个测试用例。一篇总结的题解：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/er-fen-cha-zhao-suan-fa-xi-jie-xiang-jie-by-labula/

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res={-1,-1};if(nums.size()==0) return res;
if(nums.size()==1&&nums[0]!=target) return res;
int i=0,j=nums.size()-1;
while(i<=j){//寻找右边界int mid=(i+j)/2;if(nums[mid]>target){j=mid-1;}else if(nums[mid]<target){i=mid+1;}else{i=mid+1;}
}
int right=i;
cout<<right<<endl;
if(j>0&&nums[j]!=target){res={-1,-1};return res;
}
i=0;j=nums.size()-1;
while(i<=j){//寻找左边界int mid=(i+j)/2;if(nums[mid]>target){j=mid-1;}else if(nums[mid]<target){i=mid+1;}else{j=mid-1;}
}
int left=j;
cout<<left<<endl;
res={left+1,right-1};
if(res[0]>res[1]) {res={-1,-1};return res;
}
return res;}
};