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

题解思路

1. 旋转数组的特点

旋转后的数组由 两个递增的子数组 组成，其中 最小值 是数组的 旋转点，即第二个递增子数组的 起点。

例如：

Leetcode 67.寻找旋转排序数组中的最小值-原题链接

题目内容

已知一个长度为 $n$ 的数组，预先按照升序排列，经由 $1$到 $n$ 次旋转后，得到输入数组。例如，原数组 $nums = [0,1,2,4,5,6,7]$ 在变化后可能得到：

• 若旋转 $4$ 次，则可以得到 $[4,5,6,7,0,1,2]$
• 若旋转 $7$ 次，则可以得到 $[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)$的算法解决此问题。

输入描述

• 第一行输入一个整数 n，表示数组的长度。
• 第二行输入 n 个整数，表示旋转后的数组 nums。 输出描述

输出描述

输出数组中的最小元素。

样例1

输入

5
3 4 5 1 2

输出

1

说明

原数组为$[1,2,3,4,5]$ ，旋转 $3$次得到输入数组。

样例2

输入

7
4 5 6 7 0 1 2

输出

0

说明

原数组为$[0,1,2,4,5,6,7]$ ，旋转 $4$ 次得到输入数组

样例3

输入

4
11 13 15 17

输出

11

说明

原数组为 $[11,13,15,17]$ ，旋转$4$次得到输入数组

提示：

• $n == nums.length$
• $1 <= n <= 5000$
• $-5000 <= nums[i] <= 5000$
• $nums$中的所有整数互不相同
• $nums$ 原来是一个升序排序的数组，并进行了 $1$ 至 $n$ 次旋转