手機(jī)網(wǎng)站開發(fā) pdf最新旅游熱點(diǎn)
?🌟快來參與討論💬，點(diǎn)贊👍、收藏?、分享📤，共創(chuàng)活力社區(qū)。 🌟?
別再猶豫了！快來訂閱我們的算法每日雙題精講專欄，一起踏上算法學(xué)習(xí)的精彩之旅吧💪???
?????????在算法的學(xué)習(xí)之旅中，二分查找是一種高效且經(jīng)典的算法，其應(yīng)用場景廣泛。今天我們將深入探討如何運(yùn)用二分查找來解決 “尋找旋轉(zhuǎn)排序數(shù)組中的最小值” 以及趣味十足的 “點(diǎn)名” 問題。這兩道題不僅能加深我們對二分查找的理解，還能鍛煉我們在不同場景下靈活運(yùn)用算法的能力。?
?目錄
一、尋找旋轉(zhuǎn)排序數(shù)組中的最小值
📖題目描述
🧠講解算法原理
💻代碼實(shí)現(xiàn)（以 C++ 為例）
復(fù)雜度分析
二、點(diǎn)名
📖題目描述
🧠講解算法原理
💻代碼實(shí)現(xiàn)（以 C++ 為例）
復(fù)雜度分析
一、尋找旋轉(zhuǎn)排序數(shù)組中的最小值
題目鏈接👉【力扣】
📖題目描述
?
?
?
🧠講解算法原理
對于這道題，我們可以利用二分查找來優(yōu)化時(shí)間復(fù)雜度。
????????初始化左指針 left 為 0，右指針 right 為數(shù)組長度減 1。在循環(huán)過程中，計(jì)算中間索引 mid = left + (right - left) / 2 。
比較 nums[mid] 與 nums[right] 的大小：
- 如果 nums[mid] < nums[right] ，說明最小值在 mid 及其左邊，因?yàn)?mid 到 right 這一段是有序的，最小值肯定不在這一段，所以將 right 更新為 mid 。
- 如果 nums[mid] > nums[right] ，說明最小值在 mid 的右邊，因?yàn)?mid 及其左邊這一段是有序的，最小值不在這一段，所以將 left 更新為 mid + 1 。
當(dāng) left 等于 right 時(shí)，循環(huán)結(jié)束，此時(shí) nums[left] 就是數(shù)組中的最小值。
?
💻代碼實(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];
}復(fù)雜度分析
?
- 時(shí)間復(fù)雜度：每次循環(huán)都將搜索區(qū)間縮小一半，所以時(shí)間復(fù)雜度為
，其中?
是數(shù)組的長度。相比遍歷整個(gè)數(shù)組查找最小值的暴力解法（時(shí)間復(fù)雜度為
），效率大大提高。
- 空間復(fù)雜度：只使用了常數(shù)級別的額外空間，即幾個(gè)指針變量，所以空間復(fù)雜度為
。
二、點(diǎn)名
?題目鏈接👉【力扣】
📖題目描述
?
?
?
🧠講解算法原理
這道題同樣可以借助二分查找來高效解決。
????????初始化左指針 left 為 0，右指針 right 為名單長度減 1。
????????在循環(huán)中，計(jì)算中間索引 mid = left + (right - left) / 2 。
比較中間位置的學(xué)生名字與老師點(diǎn)的名字：
- 如果相同，直接返回 mid 。
- 如果中間位置的名字小于老師點(diǎn)的名字，說明要找的名字在 mid 的右邊，將 left 更新為 mid + 1 。
- 如果中間位置的名字大于老師點(diǎn)的名字，說明要找的名字在 mid 的左邊，將 right 更新為 mid - 1 。
當(dāng) left 大于 right 時(shí)，循環(huán)結(jié)束，說明名單中沒有該學(xué)生，返回 -1 。
💻代碼實(shí)現(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;
}復(fù)雜度分析
- 時(shí)間復(fù)雜度：每次迭代都能將搜索區(qū)間縮小一半，時(shí)間復(fù)雜度為
- 空間復(fù)雜度：只使用了常數(shù)級別的額外空間，如幾個(gè)指針變量，所以空間復(fù)雜度為?
????????通過對這兩道題目的學(xué)習(xí)，我們對二分查找算法的理解和應(yīng)用能力又上了一個(gè)新臺(tái)階。在今后遇到類似問題時(shí)，要學(xué)會(huì)靈活運(yùn)用二分查找來優(yōu)化代碼的時(shí)間復(fù)雜度。
如果大家在學(xué)習(xí)過程中有任何疑問或者想法，歡迎在評論區(qū)交流分享。后續(xù)我還會(huì)帶來更多精彩的算法內(nèi)容，記得關(guān)注哦！
?