已知一个长度为 n 的数组，预先按照升序排列，经由 1到 n 次旋转后，得到输入数组。例如，原数组 nums=[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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并输出数组中的最小元素 。
你必须设计一个时间复杂度为 O(log n)的算法解决此问题。
输出数组中的最小元素。
输入
5
3 4 5 1 2
输出
1
原数组为[1,2,3,4,5] ，旋转 3次得到输入数组。
输入
7
4 5 6 7 0 1 2
输出
0
原数组为[0,1,2,4,5,6,7] ，旋转 4 次得到输入数组
输入
4
11 13 15 17
输出
11
原数组为 [11,13,15,17] ，旋转4次得到输入数组
提示：
旋转后的数组由 两个递增的子数组 组成，其中 最小值 是数组的 旋转点，即第二个递增子数组的 起点。
例如：
原数组: [0, 1, 2, 4, 5, 6, 7]
旋转后: [4, 5, 6, 7, 0, 1, 2] （最小值 0）
目标是 在 O(logn) 时间内找到这个最小值。
二分查找的关键在于 判断哪一部分是有序的，然后调整搜索范围：
nums[mid] > nums[right]，说明最小值一定在 mid 右侧，因为 mid 及其左侧仍是递增的，最小值被旋转到了右侧。nums[mid] < nums[right]，说明最小值一定在 mid 左侧或就是 mid，因为 mid 及其右侧是递增的，意味着 mid 可能是最小值。import sys
def find_min(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]: # 说明最小值在右侧
left = mid + 1
else: # 说明最小值在左侧或就是 mid
right = mid
return nums[left]
# 读取输入
n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().split()))
# 输出结果
print(find_min(nums))
import java.util.Scanner;
public class Main {
public static int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}
System.out.println(findMin(nums));
}
}
#include <iostream>
#include <vector>
using namespace std;
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
cout << findMin(nums) << endl;
return 0;
}