?🌟快來參與討論💬，點贊👍、收藏?、分享📤，共創(chuàng)活力社區(qū)。 🌟?

別再猶豫了！快來訂閱我們的算法每日雙題精講專欄，一起踏上算法學習的精彩之旅吧💪???

---

?????????在算法的學習之旅中，二分查找是一種高效且經(jīng)典的算法，其應(yīng)用場景廣泛。今天我們將深入探討如何運用二分查找來解決 “尋找旋轉(zhuǎn)排序數(shù)組中的最小值” 以及趣味十足的 “點名” 問題。這兩道題不僅能加深我們對二分查找的理解，還能鍛煉我們在不同場景下靈活運用算法的能力。?

---

?目錄

一、尋找旋轉(zhuǎn)排序數(shù)組中的最小值

📖題目描述

🧠講解算法原理

💻代碼實現(xiàn)（以 C++ 為例）

復雜度分析

二、點名

📖題目描述

🧠講解算法原理

💻代碼實現(xiàn)（以 C++ 為例）

復雜度分析

---

一、尋找旋轉(zhuǎn)排序數(shù)組中的最小值

題目鏈接👉【力扣】

📖題目描述

?

?

?

🧠講解算法原理

對于這道題，我們可以利用二分查找來優(yōu)化時間復雜度。

????????初始化左指針 left 為 0，右指針 right 為數(shù)組長度減 1。在循環(huán)過程中，計算中間索引 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 時，循環(huán)結(jié)束，此時 nums[left] 就是數(shù)組中的最小值。

?

💻代碼實現(xiàn)（以 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];
}

復雜度分析

?

• 時間復雜度：每次循環(huán)都將搜索區(qū)間縮小一半，所以時間復雜度為 ，其中? 是數(shù)組的長度。相比遍歷整個數(shù)組查找最小值的暴力解法（時間復雜度為 ），效率大大提高。

• 空間復雜度：只使用了常數(shù)級別的額外空間，即幾個指針變量，所以空間復雜度為 。

---

二、點名

?題目鏈接👉【力扣】

📖題目描述

?

?

?

🧠講解算法原理

這道題同樣可以借助二分查找來高效解決。

????????初始化左指針 left 為 0，右指針 right 為名單長度減 1。

????????在循環(huán)中，計算中間索引 mid = left + (right - left) / 2 。

比較中間位置的學生名字與老師點的名字：

• 如果相同，直接返回 mid 。

• 如果中間位置的名字小于老師點的名字，說明要找的名字在 mid 的右邊，將 left 更新為 mid + 1 。

• 如果中間位置的名字大于老師點的名字，說明要找的名字在 mid 的左邊，將 right 更新為 mid - 1 。

當 left 大于 right 時，循環(huán)結(jié)束，說明名單中沒有該學生，返回 -1 。

💻代碼實現(xiàn)（以 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;
}

復雜度分析

• 時間復雜度：每次迭代都能將搜索區(qū)間縮小一半，時間復雜度為 ，其中 是名單中學生的數(shù)量。相比逐個遍歷名單查找學生的暴力解法（時間復雜度為 ），效率大幅提升。

• 空間復雜度：只使用了常數(shù)級別的額外空間，如幾個指針變量，所以空間復雜度為?。

---

????????通過對這兩道題目的學習，我們對二分查找算法的理解和應(yīng)用能力又上了一個新臺階。在今后遇到類似問題時，要學會靈活運用二分查找來優(yōu)化代碼的時間復雜度。

如果大家在學習過程中有任何疑問或者想法，歡迎在評論區(qū)交流分享。后續(xù)我還會帶來更多精彩的算法內(nèi)容，記得關(guān)注哦！

?