假设一个排序过的数组在某个你事先不知道的枢轴上旋转 也就是说,0 1 2 4 5 6 7可能变成4 5 6 7 0 1 2 求最小元素,Java
时间: 2024-09-10 08:27:31 浏览: 41
当你需要在一个已经按照升序排列并部分旋转的数组中找到最小元素,可以采用一种简单的二分查找算法的变体。这种方法被称为“折半查找”或“二分搜索”,但由于数组可能是旋转的,你需要首先确定旋转点的位置。
以下是步骤:
1. 初始化两个指针,`left` 和 `right` 分别指向数组的第一个元素和最后一个元素。
2. 计算中间索引 `mid` = `(left + right) / 2`。
3. **检查基准**:
- 如果 `arr[mid]` 小于 `arr[right]`,说明右半部分是未旋转的部分,因为如果已旋转,较大的值会出现在左半边。所以将 `left` 设置为 `mid + 1`,继续在右半部分查找。
- 否则,如果 `arr[mid]` 大于 `arr[right]`,说明较小的元素在左半部分,将 `right` 设置为 `mid - 1`,并在左半部分继续查找。
4. 当 `left` 等于 `right` 时,找到了最小元素,返回 `arr[left]` 或者 `arr[right]`(它们相等)。
下面是Java代码实现:
```java
public int findMin(int[] nums) {
if (nums.length == 0) return 0;
int left = 0;
int right = nums.length - 1;
// 找到旋转点
while (left < right && nums[left] <= nums[right]) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid; // 已经到了最右边的非降序部分,旋转点在mid+1
} else {
left = mid + 1; // 仍然在降序部分,继续向右找
}
}
// 返回左侧或右侧的最小值
return Math.min(nums[left], nums[right]);
}
```
阅读全文