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

算法每日双题精讲 —— 二分查找（寻找旋转排序数组中的最小值，点名）

article 2025/1/29 8:03:43

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

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

在算法的学习之旅中，二分查找是一种高效且经典的算法，其应用场景广泛。今天我们将深入探讨如何运用二分查找来解决 “寻找旋转排序数组中的最小值” 以及趣味十足的 “点名” 问题。这两道题不仅能加深我们对二分查找的理解，还能锻炼我们在不同场景下灵活运用算法的能力。

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

📖题目描述

🧠讲解算法原理

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

复杂度分析

二、点名

📖题目描述

🧠讲解算法原理

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

复杂度分析

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

题目链接👉【力扣】

📖题目描述

🧠讲解算法原理

对于这道题，我们可以利用二分查找来优化时间复杂度。

初始化左指针 left 为 0，右指针 right 为数组长度减 1。在循环过程中，计算中间索引 mid = left + (right - left) / 2 。

比较 nums[mid] 与 nums[right] 的大小：

如果 nums[mid] < nums[right] ，说明最小值在 mid 及其左边，因为 mid 到 right 这一段是有序的，最小值肯定不在这一段，所以将 right 更新为 mid 。

如果 nums[mid] > nums[right] ，说明最小值在 mid 的右边，因为 mid 及其左边这一段是有序的，最小值不在这一段，所以将 left 更新为 mid + 1 。

当 left 等于 right 时，循环结束，此时 nums[left] 就是数组中的最小值。

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

#include <iostream>
#include <vector>

using namespace std;

int findMin(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[right]) {
            right = mid;
        }
        else {
            left = mid + 1;
        }
    }
    return nums[left];
}

复杂度分析

时间复杂度：每次循环都将搜索区间缩小一半，所以时间复杂度为 $O(log n)$ ，其中 $n$ 是数组的长度。相比遍历整个数组查找最小值的暴力解法（时间复杂度为 $O(n)$ ），效率大大提高。

空间复杂度：只使用了常数级别的额外空间，即几个指针变量，所以空间复杂度为 $O(1)$ 。

二、点名

题目链接👉【力扣】

📖题目描述

🧠讲解算法原理

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

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

在循环中，计算中间索引 mid = left + (right - left) / 2 。

比较中间位置的学生名字与老师点的名字：

如果相同，直接返回 mid 。

如果中间位置的名字小于老师点的名字，说明要找的名字在 mid 的右边，将 left 更新为 mid + 1 。

如果中间位置的名字大于老师点的名字，说明要找的名字在 mid 的左边，将 right 更新为 mid - 1 。

当 left 大于 right 时，循环结束，说明名单中没有该学生，返回 -1 。

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

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int rollCall(vector<string>& names, string target) {
    int left = 0, right = names.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (names[mid] == target) {
            return mid;
        }
        else if (names[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return -1;
}