算法---二分查找练习-2（寻找旋转排序数组中的最小值）
寻找旋转排序数组中的最小值
- 1. 题目解析
- 2. 讲解算法原理
- 3. 编写代码
1. 题目解析
题目地址：点这里
2. 讲解算法原理
-
首先，检查数组的最后一个元素是否大于第一个元素。如果是，说明数组没有进行旋转，直接返回第一个元素作为最小值。
-
如果数组进行了旋转，使用二分查找的思想来找到最小元素。
-
初始化两个指针 left 和 right，分别指向数组的起始位置和结束位置。
-
进入循环，循环条件为 left < right。
-
在每次循环中，计算中间元素的索引 mid，通过将左指针 left 和右指针 right 的差值除以2得到。
-
检查中间元素 nums[mid] 是否同时满足以下两个条件：
- nums[mid] < nums[mid+1]：中间元素小于其后一个元素。
- nums[mid] < nums[0]：中间元素小于数组的第一个元素。
-
如果满足这两个条件，说明最小元素在中间元素的左侧，将右指针 right 更新为 mid，继续搜索左侧。
-
如果不满足上述条件，说明最小元素在中间元素的右侧，将左指针 left 更新为 mid + 1，继续搜索右侧。
- 当循环结束时，左指针 left 指向的位置即为最小元素的索引，返回 nums[left] 即可得到最小元素的值。
3. 编写代码
class Solution {
public:int findMin(vector<int>& nums) {if(nums[nums.size()-1]>nums[0]) return nums[0];int left=0,right=nums.size()-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]<nums[mid+1] &&nums[mid]<nums[0]) right=mid;else left=mid+1;}return nums[left];}
};