📝前言說明:
- 本專欄主要記錄本人的基礎算法學習以及LeetCode刷題記錄,按專題劃分
- 每題主要記錄:(1)本人解法 + 本人屎山代碼;(2)優質解法 + 優質代碼;(3)精益求精,更好的解法和獨特的思想(如果有的話)
- 文章中的理解僅為個人理解。如有錯誤,感謝糾錯
🎬個人簡介:努力學習ing
📋本專欄:C++刷題專欄
📋其他專欄:C語言入門基礎,python入門基礎,C++學習筆記,Linux
🎀CSDN主頁 愚潤澤
視頻
- 二分查找算法介紹
- 704. 二分查找
- 樸素二分查找模板
- 34. 在排序數組中查找元素的第一個和最后一個位置
- 二分模板
二分查找算法介紹
因為我之前用python寫題的時候也寫過二分查找,也有點心得:
https://blog.csdn.net/tan_run/article/details/145514702
如今再學,任深感不足。通過 704 和 34 題再度感受和理解二分查找。
704. 二分查找
暴力解法:
遍歷數組,依次和target
比較,時間復雜度:O(n)
暴力解法的局限在于:每次只能判斷一個數,沒有利用數組升序的特點
更好的解法:二分查找。利用數組有序的特點,那怎么利用呢?
假設我們隨機取一個下標i
,將nums[i]
與target
比較,如果nums[i] < target
,又因為數組有序,所以:nums[i]
左邊的數都小于target
,我們就可以直接排除左邊的區間。
而上面所體現的也叫做二段性:每次“選點”,通過該點可以讓我們把探索區域劃分成兩份,并且能夠排除一段區域。(只是選中點的時候,數學期望最小(易證),所以我們通常取中點,也叫做二分)
樸素二分查找模板
閉區間寫法:
.......
:根據二段性的特點來填寫while(left <= right)
:因為是閉區間寫法,區間不為空,還要判斷left + (right - left) / 2
:防溢出寫法
34. 在排序數組中查找元素的第一個和最后一個位置
暴力解法:
從頭到尾遍歷數組,時間復雜度:O(n)
二分查找(利用二段性):
- 先找左端點:左端點左邊的元素 <
t
;左端點及左端點右邊的元素 >=t
。于是,我們就可以發現二段性:當nums[mid] < t
,左端點一定嚴格在mid
的右邊[mid + 1, right]
(畫圖很好理解) ,left
更新為mid + 1
;當nums[mid] >= t
的時候,左端點一定在[left, mid]
,mid
位置不能排除,因為有可能mid
就是左端點,right
更新為mid
- 上面這種方法其實是左閉右開區間的寫法,
right
所在位置已經判斷過了,循環條件為while(left < right)
,因為當left == right
的時候已經是空區間,循環不變量:right
始終指向>= t
的數字 - 求中點操作:在左閉右開這種寫法里面,當有兩個中間值時(數組長度為偶數),必須要選擇前一個:
left + (right - left) / 2
重點:以上總結找左端點>=
(左閉右開區間寫法):
- 如果
nums[mid] < t
,則右端點肯定在:[mid + 1, right]
- 如果
nums[mid] >= t
,則右端點肯定在:[left, mid]
- 循環條件,
while(left < right)
(因為是左閉右開的) - 求中點操作:
left + (right - left) / 2
取前面的中點 - 循環不變量:
right
始終指向第一個>= t
的數
PS:多舉例子,找極端例子看特殊情況
當然我們也可以直接寫找右端點<=
的:
- 如果
nums[mid] <= t
,則右端點肯定在:[mid, right]
- 如果
nums[mid] > t
,則右端點肯定在:[left, mid - 1]
- 循環條件,
while(left < right)
(因為是左開右閉) - 求中點操作:
left + (right - left + 1) / 2
取后面的中點
其他方法:在>=
的基礎上轉換:
題解代碼:
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size() == 0){return {-1, -1};}// 二分左端點 >= int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2; // 防止溢出if(nums[mid] < target)left = mid + 1;elseright = mid;}if(nums[right] != target)return {-1, -1}; // 代表沒有targetint begin = right;// 找右端點(左端點不重置)left = begin, right = nums.size() - 1;while(left < right){int mid = left + (right - left + 1) / 2;if(nums[mid] <= target)left = mid;elseright = mid - 1;}return {begin, right};}
};
二分模板
口訣:
mid
:下面出現-1
,上面就要+1
if...else...
:根據二段性寫出
為什么呢?
首先,左右兩種模板的取mid
區別是:左邊是向下取整,右邊是向上取整
以右邊模板為例:
右邊模板的收縮范圍:[mid, right]
或 [left, mid - 1]
如果此時剩余區間為:[right - 1, right]
,向下取整則mid = right - 1
。如果,最后的判斷進入if
,則left = mid = right - 1
和原來無異,就會死循環。
如果是向上取整:mid = right
,進入if
:left = right
,進入else
:right = right - 1
,兩條語句都變化了,就不會死循環
🌈我的分享也就到此結束啦🌈
要是我的分享也能對你的學習起到幫助,那簡直是太酷啦!
若有不足,還請大家多多指正,我們一起學習交流!
📢公主,王子:點贊👍→收藏?→關注🔍
感謝大家的觀看和支持!祝大家都能得償所愿,天天開心!!!