刷题笔记:力扣第153题-寻找旋转排序数组中的最小值

1.本题和力扣第33题-搜索旋转排序数组很像，都是将原本升序的数组在某一个节点进行旋转，在旋转后的数组中做文章。核心思路为通过二分区分升序和乱序部分，若nums[l] < nums[mid]则说明左边是升序，右边是乱序，那么就可以将存储的结果值与nums[l]进行大小比较，若更小就更新该值；之后再将边界收缩到右边，因为只有可能在乱序中出现更小的元素。反之亦然。

2.基于以上思想，可写出完整代码如下：

1. int findMin(int* nums, int numsSize) {
2. int res = INT_MAX;
3. int l = 0, r = numsSize – 1;
4. while (l < r){
5. int mid = (l + r) >> 1;
6.
7. if (nums[l] < nums[mid]){
8. res = fmin(res, nums[l]);
9. l = mid + 1;
10. } else {
11. res = fmin(res, nums[mid]);
12. r = mid – 1;
13. }
14. }
15.
16. return res;
17. }

本地测试通过了，但是提交后没有全部通过，错误如下：

出现这种情况的原因是当数组中只有一个元素时，l == r，代码运行时根本没有进入循环，直接输出了INT_MAX导致报错。且一定不能改成l <= r，当数组元素为，[2, 1]时会跳过1输出2，同样会报错。

3.出现这种问题的核心原因是C语言中mid是向下取整的，一旦mid == l，程序就会直接进入else分支判断，强制将右边界左移，这就导致如果最小的元素恰好在右边那个位置就会被直接跳过。所以本题的标准解法是通过判断nums[mid] > nums[r]来判断有序和乱序。完整代码如下：

1. // 寻找旋转排序数组最小值，记录最小值版本
2. int findMin(int* nums, int numsSize) {
3. int res = INT_MAX;
4. int l = 0, r = numsSize – 1;
5. while (l < r){
6. int mid = (l + r) >> 1;
7. if (nums[mid] > nums[r]){
8. // mid在左半递增区间，最小值不可能在mid，至少在mid+1右侧
9. res = fmin(res, nums[l]);
10. l = mid + 1;
11. } else {
12. // mid在右半递增区间，最小值可能就是mid
13. res = fmin(res, nums[mid]);
14. r = mid;
15. }
16. }
17. // 循环结束 l==r，还要比较最后这个位置
18. res = fmin(res, nums[l]);
19. return res;
20. }

该算法时间复杂度为O(logn)，空间复杂度为O(1)。在循环结束必须再执行一次res = fmin(res, nums[l])，避免最后剩下的那个元素就是最终答案。

4.二分法最好少加额外变量，容易在边界问题上出错。本题最标准的写法是直接返回最终两指针停下位置的元素即可，不需要res。完整代码如下：

1. // 寻找旋转排序数组中的最小值
2. int findMin(int* nums, int numsSize) {
3. int l = 0, r = numsSize – 1;
4. while (l < r){
5. int mid = (l + r) >> 1; // mid = (l+r)/2，右移等价除以2
6. if (nums[mid] > nums[r]){
7. // mid值大于右端点，说明最小值一定在mid右侧
8. l = mid + 1;
9. } else {
10. // mid <= r，最小值在mid或者mid左侧
11. r = mid;
12. }
13. }
14. // 循环结束 l == r，指向最小值
15. return nums[l];
16. }