在旋转排序数组中查找最小值

“旋转排序数组中的查找最小值”是一个流行的面试问题，用于测试候选人的解决问题的能力。

由 摩根士丹利、亚马逊、微软、三星、Adobe 等公司在 SDE 面试中提问。

旋转排序数组是指数组向前或向后移动了 k 个位置，或者旋转了 1 到 n 次。

任务是在 Log(n) 时间内 找到数组中的最小值。

例如

方法 1：线性搜索

最简单的方法是遍历数组查找最小值。该方法的时间复杂度为 O(n)，其中 n 是数组的大小。这种方法很简单，但对于大型数组来说效率不够高。

线性搜索的 Python 代码

输出

方法 2：二分查找

一种更有效的方法是利用旋转排序数组的性质并应用二分查找来找到最小值。

该算法可总结如下：

1. 初始化两个指针，“low” 和 “high”，分别指向数组的开头和结尾。
2. 检查数组是否已排序（即 low 索引处的元素小于或等于 high 索引处的元素）。如果为真，则最小值位于 low 索引处，我们可以返回它。
3. 将 mid 索引计算为 (low + high) // 2，并将该索引处的元素存储起来。
4. 将 mid 元素与 low 和 high 索引处的元素进行比较
5. 如果 mid 元素大于 high 索引处的元素，则最小值位于数组的右半部分。将“low”指针移动到 mid + 1。
6. 否则，最小值位于数组的左半部分。将“high”指针移动到 mid。
7. 重复步骤 2-4，直到“low”和“high”指针相等，这表示已找到最小值。

查找旋转排序数组中最小元素的 Python 实现

输出

时间复杂度 = O(log n)，其中 n 是数组的大小。

二分查找使我们能够有效地在每次迭代中排除一半的数组，从而得到一个更快的解决方案。

查找旋转排序数组中最小元素的 C++ 实现

输出

查找旋转排序数组中最小元素的 C 实现

输出

该方法的时间复杂度也为 O(log n)，它为在旋转排序数组中查找最小值提供了一个优化的解决方案。

结论

总之，理解旋转排序数组的概念并利用二分查找等高效算法可以极大地提高在此类数组中查找最小值的性能。熟悉这些方法将有助于候选人解决类似的面试问题，并向潜在雇主展示他们的解决问题的能力。