手機網(wǎng)站開發(fā) pdf最新旅游熱點
?🌟快來參與討論💬，點贊👍、收藏?、分享📤，共創(chuàng)活力社區(qū)。 🌟?
別再猶豫了！快來訂閱我們的算法每日雙題精講專欄，一起踏上算法學習的精彩之旅吧💪???
?????????在算法的學習之旅中，二分查找是一種高效且經(jīng)典的算法，其應用場景廣泛。今天我們將深入探討如何運用二分查找來解決 “尋找旋轉排序數(shù)組中的最小值” 以及趣味十足的 “點名” 問題。這兩道題不僅能加深我們對二分查找的理解，還能鍛煉我們在不同場景下靈活運用算法的能力。?
?目錄
一、尋找旋轉排序數(shù)組中的最小值
📖題目描述
🧠講解算法原理
💻代碼實現(xiàn)（以 C++ 為例）
復雜度分析
二、點名
📖題目描述
🧠講解算法原理
💻代碼實現(xiàn)（以 C++ 為例）
復雜度分析
一、尋找旋轉排序數(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)結束，此時 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)結束，說明名單中沒有該學生，返回 -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ù)級別的額外空間，如幾個指針變量，所以空間復雜度為?
????????通過對這兩道題目的學習，我們對二分查找算法的理解和應用能力又上了一個新臺階。在今后遇到類似問題時，要學會靈活運用二分查找來優(yōu)化代碼的時間復雜度。
如果大家在學習過程中有任何疑問或者想法，歡迎在評論區(qū)交流分享。后續(xù)我還會帶來更多精彩的算法內(nèi)容，記得關注哦！
?