给定一个由不同元素组成的已排序数组 arr[]，其大小为 n，该数组在某个未知的点进行了旋转。我们的任务是在其中找到最小元素。
示例：
> 输入： arr[] = [5, 6, 1, 2, 3, 4]
> 输出： 1
> 解释： 1 是数组中存在的最小元素。
>
> 输入： arr[] = [3, 1, 2]
> 输出： 1
> 解释：1 是数组中存在的最小元素。
>
> 输入： arr[] = [4, 2, 3]
> 输出： 2
> 解释： 2 是数组中唯一的（即最小的）元素。
目录
- [朴素方法] 线性搜索 – O(n) 时间复杂度和 O(1) 空间复杂度
- [预期方法] 二分搜索 – O(log n) 时间复杂度和 O(1) 空间复杂度
[朴素方法] 线性搜索 – O(n) 时间和 O(1) 空间
一个简单的解决方案是使用线性搜索遍历整个数组并找到最小值。
C++
CODEBLOCK_baae8de6
C
CODEBLOCK_7c9b190b
Java
CODEBLOCK_839ac885
Python
CODEBLOCK_707992a1
C#
CODEBLOCK_39a5d363
JavaScript
CODEBLOCK_ec7036a6
输出
1
[预期方法] 二分搜索 – O(log n) 时间和 O(1) 空间
> 我们可以使用二分搜索来优化最小元素的搜索过程。我们会找到中间元素 (mid)，然后决定是停止搜索，还是向左半部分或右半部分继续搜索：
>
> – 如果 arr[mid] > arr[high]，这意味着 arr[low … mid] 是已排序的，我们需要在右半部分搜索。因此，我们调整 low = mid + 1。
> – 如果 arr[mid] <= arr[high]，这意味着 arr[mid … high] 是已排序的，我们需要在左半部分搜索。因此，我们调整 high = mid。(注意：当前的 mid 可能就是最小元素)。
>
> 我们如何终止搜索呢？一种方法是检查 mid 是否比其相邻的两个元素都小，如果是，则返回 mid。但这需要进行大量的条件检查，例如相邻索引是否有效等。