目录
题目概述(简单难度)
题目链接:
思路与代码
思路展现
使用经典二分法,题解直接看此链接即可:
代码示例
注意此处我们将代码进行了改动,并附上改动原因
public class Solution { // [3, 4, 5, 1, 2] // [1, 2, 3, 4, 5] // 不能使用左边数与中间数比较,这种做法不能有效地减治 // [1, 2, 3, 4, 5] // [3, 4, 5, 1, 2] // [2, 3, 4, 5 ,1] public int minArray(int[] numbers) { int len = numbers.length; if (len == 0) { return 0; } int left = 0; int right = len - 1; while (left <= right) { int mid = (left + right) / 2; if (numbers[mid] > numbers[right]) { // [3, 4, 5, 1, 2],mid 以及 mid 的左边一定不是最小数字 // 下一轮搜索区间是 [mid + 1, right] left = mid + 1; } else if (numbers[mid] == numbers[right]) { // 只能把 right 排除掉,下一轮搜索区间是 [left, right - 1] right = right - 1; } else { // 此时 numbers[mid] < numbers[right] // mid 的右边一定不是最小数字,mid 有可能是,下一轮搜索区间是 [left, mid] right = mid; } } // 最小数字一定在数组中,因此不用后处理 return numbers[left]; } }
注意事项
1:
注意此处我们再求中间下标的时候会有很多种求法,例如如下写法:
int mid = left + (right - left) / 2
原因如下所示:
2:
这里的符号即可写小于号,也可以写小于等于号.
while (left <= right)