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

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

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

---

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

---

 目录

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

📖题目描述

🧠讲解算法原理

💻代码实现（以 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];
}

复杂度分析

 

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

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

---

二、点名

 题目链接👉【力扣】

📖题目描述

 

 

 

🧠讲解算法原理

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

        初始化左指针 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;
}

复杂度分析

• 时间复杂度：每次迭代都能将搜索区间缩小一半，时间复杂度为 ，其中 是名单中学生的数量。相比逐个遍历名单查找学生的暴力解法（时间复杂度为 ），效率大幅提升。

• 空间复杂度：只使用了常数级别的额外空间，如几个指针变量，所以空间复杂度为 。

---

        通过对这两道题目的学习，我们对二分查找算法的理解和应用能力又上了一个新台阶。在今后遇到类似问题时，要学会灵活运用二分查找来优化代码的时间复杂度。

如果大家在学习过程中有任何疑问或者想法，欢迎在评论区交流分享。后续我还会带来更多精彩的算法内容，记得关注哦！