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.

You may assume no duplicate exists in the array.

这题其实就是找翻转后右侧部分的最左端点，典型的二分搜索变体，大致思路分成两种情况讨论：

1）如果搜索范围在翻转部分，稍微复杂一点：

1.1）如果中间点在翻转后的左侧，则应该往右寻找，因为如果没有冗余元素，最小值不可能出现在左侧；

1.2）如果中间点在翻转后的右侧，则应该往左寻找。不过这时应该缓存下当前中间点对应的元素，因为再往左的话，可能就到了翻转后的左侧部分，就可能错过全局最小值了。

2）如果搜索范围在排序的部分，则当前的最小值肯定是在最左端。不过这个时候最左端的值不一定是全局最小，需要跟缓存的最小值在进行一次比较。

	public int findMin(int[] num) {
		int low = 0, high = num.length - 1;
		int ret = Integer.MAX_VALUE;

		while (low <= high) {
			int mid = low + (high - low) / 2;
			// On the sorted part.
			if (num[low] <= num[high]) {
				return Math.min(num[low], ret);
			} else { // On the rotated part.
				// num[mid] is on the left rotated part.
				if (num[mid] >= num[low]) {
					low = mid + 1;
				} else { // num[mid] is on the right rotated part.
					ret = num[mid];
					high = mid - 1;
				}
			}
		}
 	return ret;
	}

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

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.

	public int findMin(int[] num) {
		int low = 0, high = num.length - 1;
		int ret = Integer.MAX_VALUE;

		while (low <= high) {
			// Linear scan to find a non-flat part.
			if (num[low] == num[high]) {
				ret = Math.min(num[low], ret);
				low++;
				continue;
			}
			int mid = low + (high - low) / 2;
			// On the sorted part.
			if (num[low] < num[high]) {
				return Math.min(num[low], ret);
			} else { // On the rotated part.
				// num[mid] is on the left rotated part.
				if (num[mid] >= num[low]) {
					low = mid + 1;
				} else { // num[mid] is on the right rotated part.
					ret = num[mid];
					high = mid - 1;
				}
			}
		}
		return ret;
	}

[LeetCode] Find Minimum in Rotated Sorted Array