AlgoPressAppearance
11-旋转数组的最小数字
题目描述
https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
示例 1：
输入：[3,4,5,1,2]
输出：1
示例 2：
输入：[2,2,2,0,1]
输出：0
注意：本题与主站 154 题相同：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/
思路分析
旋转数组在旋转之前，是递增的，第一个数是最小。 当旋转之后，如果找到一个数，它小于前面的数，那么说明他就是旋转数组中最小的数。
使用二分法查找。 二分之后，如果最左边的数大于最后边的数，那么说明最小数字就在此数组中。
实现代码
csharp
public class Solution {
public int MinArray(int[] numbers) {
int left = 0;
int right = numbers.Length - 1;
while(left < right){
int mid = left + (right - left) / 2;
if(numbers[mid] < numbers[right]){
right = mid;
}
else if(numbers[mid] > numbers[right]){
left = mid + 1;
}
else{ //相等:不能随意舍弃一半
right--;
}
}
return numbers[left];
}
}
复习代码:20220503
csharp
public class Solution {
public int FindMin(int[] nums) {
//二分查找
int left = 0;
int right = nums.Length-1;
while(left<right){
int mid = left + (right - left) / 2;
//正常情况下， mid 是要小于 right 的，如果 mid > right 说明 旋转位置在右边，即最小值在右边
//所以排除左边的值，不包含 mid
if(nums[mid] > nums[right]){
left = mid + 1;
}
//注意如果 mid 小于右边的时候， mid 还是有可能成为结果的，所以 right = mid
else if(nums[mid] < nums[right]){
right = mid;
}
//如果 mid 和 right 相等，则无法直接得出结果(最左边的一个)，所以 right --
else{
right--;
}
}
return nums[left];
}
}