153. 寻找旋转排序数组中的最小值
描述
已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:
若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]
注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
链接
153. 寻找旋转排序数组中的最小值 - 力扣(LeetCode) (leetcode-cn.com)
解法:二分法
注意需要处理一下细节
1 class Solution { 2 public int findMin(int[] nums) { 3 int left = 0, right = nums.length - 1; 4 while (left < right) { 5 int mid = left + (right - left) / 2; 6 7 // 假如 nums[mid] >= nums[right],说明 nums[mid]左侧是 升序区间,右侧是 无序区间 8 // 那么 最小值会存在 无序区间那块 9 if(nums[mid] >= nums[right]) { 10 left = mid + 1; 11 } 12 /* 由于nums[mid]可能就是目标值, 13 假设 最小值为 target,那么 nums[mid] = target, 14 就直接return mid,意味着 right边界应该含有mid值*/ 15 else { 16 right = mid; 17 } 18 } 19 return nums[left]; 20 } 21 }
1 class Solution { 2 public int findMin(int[] nums) { 3 int left = 0, right = nums.length - 1; 4 while (left <= right) { 5 int mid = left + (right - left) / 2; 6 7 // 假如 nums[mid] >= nums[right],说明 nums[mid]左侧是 升序区间,右侧是 无序区间 8 // 那么 最小值会存在 无序区间那块 9 if(nums[mid] >= nums[right]) { 10 left = mid + 1; 11 } 12 /* 由于nums[mid]可能就是目标值, 13 假设 最小值为 target,那么 nums[mid] = target, 14 就直接return mid,意味着 right边界应该含有mid值*/ 15 else { 16 right = mid; 17 } 18 } 19 return nums[left]; 20 } 21 }
这个时候(while (left <= right)),需要 return nums[right]
1 class Solution { 2 public int findMin(int[] nums) { 3 int left = 0, right = nums.length - 1; 4 while (left <= right) { 5 int mid = left + (right - left) / 2; 6 7 // 假如 nums[mid] >= nums[right],说明 nums[mid]左侧是 升序区间,右侧是 无序区间 8 // 那么 最小值会存在 无序区间那块 9 if(nums[mid] >= nums[right]) { 10 left = mid + 1; 11 } 12 /* 由于nums[mid]可能就是目标值, 13 假设 最小值为 target,那么 nums[mid] = target, 14 就直接return mid,意味着 right边界应该含有mid值*/ 15 else { 16 right = mid; 17 } 18 } 19 return nums[right]; 20 } 21 }
总结
1、最小值会在 mid 无序区间的 那侧,因此,right = mid 为起始
2、while (left < right) ,出循环的时候是 left = right,此时 left = right = mid,可以return nums[left,也可以是 return nums[right];
但 while (left <= right)时,此时出 循环是 left > right,所以应当 return nums[right]
可以看下面代码输出
1 class Solution { 2 public int findMin(int[] nums) { 3 int left = 0, right = nums.length - 1; 4 while (left <= right) { 5 int mid = left + (right - left) / 2; 6 7 // 假如 nums[mid] >= nums[right],说明 nums[mid]左侧是 升序区间,右侧是 无序区间 8 // 那么 最小值会存在 无序区间那块 9 if(nums[mid] >= nums[right]) { 10 left = mid + 1; 11 } 12 /* 由于nums[mid]可能就是目标值, 13 假设 最小值为 target,那么 nums[mid] = target, 14 就直接return mid,意味着 right边界应该含有mid值*/ 15 else { 16 right = mid; 17 } 18 System.out.println("nums[mid]:" + nums[mid]); 19 } 20 System.out.println("nums[left]:" + nums[left]); 21 System.out.println("nums[right]:" + nums[right]); 22 23 return nums[right]; 24 } 25 }