当前位置：首页 > article >正文

算法每日双题精讲 —— 二分查找（山脉数组的峰顶索引，寻找峰值）

article 2025/1/26 21:52:33

🌟快来参与讨论💬，点赞👍、收藏⭐、分享📤，共创活力社区。 🌟

别再犹豫了！快来订阅我们的算法每日双题精讲专栏，一起踏上算法学习的精彩之旅吧💪

在算法的广袤世界里，二分查找算法凭借其高效性与独特的解题思路，成为众多开发者和算法爱好者的得力工具。今天，让我们一同深入研究 “山脉数组的峰顶索引” 以及 “寻找峰值” 这两道经典题目，探索二分查找算法在其中的巧妙应用。

一、山脉数组的峰顶索引

📖题目描述

🧠讲解算法原理

💻代码实现（以C++为例）

复杂度分析

二、寻找峰值

📖题目描述

🧠讲解算法原理

💻代码实现（以 C++ 为例）

复杂度分析

一、山脉数组的峰顶索引

题目链接👉【力扣】

📖题目描述

🧠讲解算法原理

对于这道题，我们可以利用二分查找的思想来高效地找到山脉数组的峰顶索引。

首先，初始化左指针 left 为 1，右指针 right 为数组长度减 2。这是因为数组两端的元素不可能是峰顶（根据山脉数组的定义）。

在循环过程中，计算中间索引 mid = left + (right - left) / 2。然后比较 arr[mid] 与 arr[mid + 1] 的大小关系：

如果 arr[mid] < arr[mid + 1]，说明当前位置在上升坡，峰顶在 mid 的右侧，所以将 left 更新为 mid + 1。
如果 arr[mid] > arr[mid + 1]，说明当前位置在下降坡或者已经是峰顶，峰顶在 mid 及其左侧，将 right 更新为 mid。

当 left 等于 right 时，循环结束，此时 left（或 right）所指向的索引就是山脉数组的峰顶索引。

💻代码实现（以C++为例）

#include <iostream>
#include <vector>

using namespace std;

// 寻找山脉数组的峰顶索引
int peakIndexInMountainArray(vector<int>& arr) {
    int left = 1, right = arr.size() - 2;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < arr[mid + 1]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

int main() {
    vector<int> arr = {0, 1, 0};
    int result = peakIndexInMountainArray(arr);
    cout << "山脉数组的峰顶索引是: " << result << endl;
    return 0;
}

复杂度分析

时间复杂度：每次循环都将搜索区间缩小一半，所以时间复杂度为 $O(logn)$ ，其中是数组的长度。相比从数组头部到尾部逐个遍历查找峰顶的暴力解法（时间复杂度为 $O(n)$ ），效率有显著提升。
空间复杂度：整个过程只使用了几个额外的变量来存储指针和中间索引，不需要额外的复杂数据结构，空间复杂度为 $O(1)$ ，在空间利用上非常高效。

二、寻找峰值

题目链接👉【力扣】

📖题目描述

🧠讲解算法原理

这道题同样可以借助二分查找来解决。

初始化左指针 left 为 0，右指针 right 为数组长度减 1。

在循环中，计算中间索引 mid = left + (right - left) // 2。接着比较 nums[mid] 与 nums[mid + 1] 的大小：

若 nums[mid] < nums[mid + 1]，说明峰值在 mid 的右侧，将 left 更新为 mid + 1。
若 nums[mid] > nums[mid + 1]，说明峰值在 mid 及其左侧，将 right 更新为 mid。

当 left 等于 right 时，循环结束，此时返回的 left（或 right）就是一个峰值的索引。因为根据假设，数组两端虚拟的负无穷保证了一定能找到峰值。

💻代码实现（以 C++ 为例）

#include <iostream>
#include <vector>

using namespace std;

// 寻找峰值元素的索引
int findPeakElement(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[mid + 1]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

int main() {
    vector<int> nums = {1, 2, 3, 1};
    int result = findPeakElement(nums);
    cout << "一个峰值元素的索引是: " << result << endl;
    return 0;
}

复杂度分析

时间复杂度：由于每次迭代都能将搜索区间缩小一半，时间复杂度为 $O(logn)$ ，其中 $n$ 是数组的长度。这种方式比遍历整个数组查找峰值（时间复杂度为）要快得多。
空间复杂度：仅使用了几个简单的变量来存储指针和中间索引，没有使用额外的复杂数据结构，空间复杂度为 $O(1)$ ，在空间上非常节省。