[LintCode/LeetCode] Find Minimum in Rotated Sorted Array I & II

NO IMAGE

Find Minimum in Rotated Sorted Array

Problem

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

Notice

You may assume no duplicate exists in the array.

Example

Given [4, 5, 6, 7, 0, 1, 2]

上面的例子分別是較小元素,最小元素,較大元素,中位數在中點的情況。可見,用隊首元素num[start]和中點num[mid]比較沒有意義。因此,只判斷終點和中點元素的大小關係即可。

Solution

public class Solution {
public int findMin(int[] num) {
int start = 0, end = num.length - 1;
while (start   1 < end) {
int mid = start   (end - start) / 2;
if (num[end] > num[mid]) end = mid;
else start = mid;
}
return num[start] < num[end] ? num[start] : num[end];
}
}

Find Minimum in Rotated Sorted Array

Problem

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Example

Given [4,4,5,6,7,0,1,2]

上面這些case是很難直接用二分法判斷的,只能對中點兩邊同時使用二分法遞迴,或者完全遍歷陣列求最優解。
二分法遞迴的步驟是:建立helper()

暴力迴圈

public class Solution {
public int findMin(int[] num) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < num.length; i  ) {
min = Math.min(num[i], min);
}
return min;
}
}