寻找旋转排序数组中的最小值

题意

假设一个旋转排序的数组其起始位置是未知的(比如 0 1 2 4 5 6 7 可能变成是 4 5 6 7 0 1 2)。

你需要找到其中最小的元素。

你可以假设数组中不存在重复的元素。

样例

给出 [4,5,6,7,0,1,2] 返回 0

代码实现: 顺序查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
/**
* @param nums: a rotated sorted array
* @return: the minimum number in the array
*/
public int findMin(int[] nums) {
int i = nums[0];
for(int j = 1; j < nums.length; j++ ) {
if(nums[j] < i)
i = nums[j];
}
return i;
}
}

这种方式非常简单,就是依次顺序查找,但是题目推荐的是用二分法进行查找,故下方又用二分法实现了功能。

代码实现: 二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
/**
* @param nums: a rotated sorted array
* @return: the minimum number in the array
*/
public int findMin(int[] nums) {
int l = 0;
int r = nums.length-1;
if (nums[l] < nums[r])
return nums[l];

while (l < r) {
int mid = (l + r) / 2;
if (nums[mid] > nums[r])
l = mid + 1;
else
r = mid;
}

return nums[r];
}
}

该题的主要思路就是 中位数右侧数 的比较。
根据该类型数据的规律可得结论: 中位数 > 右侧数 则说明 最小数 在右侧,反之在左侧。

原题地址

LintCode:寻找旋转排序数组中的最小值