Day75 | 灵神 | 二分查找 寻找旋转排序数组中的最小值 搜索旋转排序数组
笔者个人博客网站：标签: 二分查找 | Darlingの妙妙屋
153.寻找旋转排序数组中的最小值
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
思路：
思路就是如何判断nums[mid]是在最小值的左侧还是右侧
这道题第一次做还是没啥思路，看到灵神说和最后一个数a进行比较就懂了
不管旋转没有旋转，只要nums[mid]<=a，那说明最小值肯定在[l,mid]之中
只要nums[mid]>a，那说明最小值肯定在[mid,r)之中
具体看灵神怎么说：
我们需要判断 x 和数组最小值的位置关系，谁在左边，谁在右边？
把 x 与最后一个数 nums[n−1] 比大小：
如果 x>nums[n−1]，那么可以推出以下结论：
1.nums 一定被分成左右两个递增段；
2.第一段的所有元素均大于第二段的所有元素；
3.x 在第一段。
4.最小值在第二段。
所以 x 一定在最小值的左边。
如果 x≤nums[n−1]，那么 x 一定在第二段。（或者 nums 就是递增数组，此时只有一段。）
x 要么是最小值，要么在最小值右边。
所以，只需要比较 x 和 nums[n−1] 的大小关系，就间接地知道了 x 和数组最小值的位置关系，从而不断地缩小数组最小值所在位置的范围，二分找到数组最小值。
完整代码：
笔者写的左闭右开区间
class Solution {
public:int findMin(vector<int>& nums) {int l=0,r=nums.size();int num=nums[r-1];while(l<r){int mid=l+(r-l)/2;if(nums[mid]<=num)r=mid;elsel=mid+1;}return nums[l];}
};
33.搜索旋转排序数组
33. 搜索旋转排序数组 - 力扣（LeetCode）
思路：
如果笔者直接做这个题那可能就蒙圈了，但是笔者是做了153才来做的
所以一下就想到找最小值然后分成两段再进行两次二分这个思路
直接开干得到如下代码
class Solution {
public://找最小值int findMin(vector<int>& nums){int l=0,r=nums.size();int num=nums[r-1];while(l<r){int mid=l+(r-l)/2;if(nums[mid]<=num)r=mid;elsel=mid+1;}return r;}//二分查找int b_search(vector<int>& nums, int l,int r,int target){while(l<r) {int mid=l+(r-l)/2;if(target<=nums[mid])r=mid;elsel=mid+1;}return (l<nums.size()&&nums[l]==target)?l:-1;}int search(vector<int>& nums, int target) {//找最小值的下标int l=findMin(nums);//说明数组被分成了两段递增if(l!=0){//搜索后面一段int a=b_search(nums,l,nums.size(),target);//搜索前面一段int b=b_search(nums,0,l,target);//哪段里面找到了返回哪段return a!=-1?a:b;}//说明数组没有被分开，搜索整个数组elsereturn b_search(nums,0,nums.size(),target);}
};
需要注意我在二分查找target中写的l和nums.size()的关系判断，因为我用的是左闭右开区间，所以如果最后没找到target的话，并且数组大小为1，那最后l==r==nums.size()了，就会越界
而灵神的判断比我更加精巧，只用了两次二分，一次查找最小，一次找target
if(target>nums.back())return b_search(nums,0,index,target);return b_search(nums,index,nums.size(),target);
target>nums.back()，如果数组只有一段，那说明数组中没有target，传入的其实是l=0,r=0
如果数组有两段，第一段的所有数字都大于第二段，那target肯定就是在第一段或者不存在，那就是[0，index)
target<=nums.back()，如果数组只有一段，那肯定数组中有target，传入的其实实际上是l=0,r=nums.size()，即搜索整个数组，如果数组有两段，第一段的所有数字都大于第二段，所以target肯定在第二段，传入的就是l=index,r=nums.size()
完整代码：
class Solution {
public:int b_search(vector<int>& nums, int l,int r,int target){while(l<r) {int mid=l+(r-l)/2;if(target<=nums[mid])r=mid;elsel=mid+1;}return nums[l]==target?l:-1;}int findMin(vector<int>& nums){int l=0,r=nums.size();int num=nums[r-1];while(l<r){int mid=l+(r-l)/2;if(nums[mid]<=num)r=mid;elsel=mid+1;}return r;}int search(vector<int>& nums, int target) {int index=findMin(nums);if(target>nums.back())return b_search(nums,0,index,target);return b_search(nums,index,nums.size(),target);}
};
