【專題刷題】二分查找(一):深度解刨二分思想和二分模板

📝前言說明:

  • 本專欄主要記錄本人的基礎算法學習以及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,進入ifleft = right,進入elseright = right - 1,兩條語句都變化了,就不會死循環


🌈我的分享也就到此結束啦🌈
要是我的分享也能對你的學習起到幫助,那簡直是太酷啦!
若有不足,還請大家多多指正,我們一起學習交流!
📢公主,王子:點贊👍→收藏?→關注🔍
感謝大家的觀看和支持!祝大家都能得償所愿,天天開心!!!

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/bicheng/78154.shtml
繁體地址,請注明出處:http://hk.pswp.cn/bicheng/78154.shtml
英文地址,請注明出處:http://en.pswp.cn/bicheng/78154.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

鄉村治理數字化平臺:信息技術賦能鄉村振興的深度探索

在信息化技術飛速發展的背景下&#xff0c;數字化轉型已成為推動社會進步和治理現代化的關鍵力量。鄉村治理數字化平臺&#xff0c;作為信息技術在鄉村治理領域的深度應用&#xff0c;正逐步成為提升鄉村治理效能、推動鄉村振興的重要工具。本文將深入探討鄉村治理數字化平臺的…

PyQt6基礎_QTabWidget

目錄 代碼 運行 官方文檔 PySide6.QtWidgets.QTabWidget - Qt for Python 代碼 class TempWidget(QWidget):def __init__(self):super().__init__()self.tabs QTabWidget()self.tabs.tabBarClicked.connect(self.tabs_tabBarClicked)widget_tab1 QWidget()widget_tab2…

springboot在eclipse里面運行 run as 是Java Application還是 Maven

在 Eclipse 里運行 Spring Boot 項目時&#xff0c;既可以選擇以“Java Application”方式運行&#xff0c;也可以通過 Maven 命令來運行&#xff0c;下面為你詳細介紹這兩種方式及適用場景。 以“Java Application”方式運行 操作步驟 在項目中找到帶有 SpringBootApplicat…

怎樣記憶Precision、Recall?

首先&#xff0c;明確符號&#xff1a; TP(True Posive)&#xff1a;標簽為正&#xff0c;預測為正 TN(True Negative)&#xff1a;標簽為負&#xff0c;預測為負 FP(False Positive)&#xff1a;標簽為負&#xff0c;預測為正 FN(False Negative)&#xff1a;標簽為正&#xf…

【C語言】C語言動態內存管理

前言 在C語言編程中&#xff0c;內存管理一直是程序員需要重點關注的領域。動態內存管理更是如此&#xff0c;它不僅涉及到內存的靈活分配和釋放&#xff0c;還隱藏著許多潛在的陷阱。本文將從動態內存分配的基礎講起&#xff0c;逐步深入到常見的錯誤、經典筆試題分析&#x…

expres路由模塊化

Express 路由模塊化是實際開發中非常重要的一部分&#xff0c;可以讓你的項目結構更清晰、維護更方便。 &#x1f9f1; 一、為什么要模塊化&#xff1f; 隨著項目變大&#xff0c;如果所有路由都寫在 app.js 中&#xff0c;會很亂。使用模塊化后可以&#xff1a; 功能解耦&a…

C語言——填充矩陣

C語言——填充矩陣 一、問題描述二、格式要求1.輸入形式2.輸出形式3.樣例 三、實驗代碼 一、問題描述 編程實現自動填充nn矩陣元素數值&#xff0c;填充規則為&#xff1a;從第一行最后一列矩陣元素開始按逆時針方向螺旋式填充數值1&#xff0c;2&#xff0c;…&#xff0c;nn…

零基礎上手Python數據分析 (22)案例實戰]之利用 Matplotlib Seaborn 進行電商銷售數據可視化分析

寫在前面 —— 圖表為刃,洞察先行!綜合運用 Pandas、Matplotlib 與 Seaborn,點亮數據價值 本篇通過一個完整的案例實戰,體驗如何將數據分析與數據可視化緊密結合,讓冰冷的數據轉化為生動、直觀、富有洞察力的視覺故事! 案例目標: 本篇博客將延續我們在第 17 篇案例中…

Java開發經驗總結

只要刪繁、捋清脈絡&#xff0c;才能掌握本質&#xff01;只有創新才有價值&#xff0c;保持創新、保持學習&#xff01; 計劃&#xff1a;UNIAPPSPRINGBOOT學習、SPRINGBOOTVUE新版學習、頁面展示學習、PYTHON。 ***********************************************************…

深入解析:RocketMQ、RabbitMQ和Kafka的區別與使用場景

互聯網大廠Java求職者面試&#xff1a;RocketMQ、RabbitMQ和Kafka的深入解析 故事場景&#xff1a;嚴肅且專業的面試官與架構師程序員馬架構 在一家知名的互聯網大廠&#xff0c;Java求職者正在接受一場嚴格的面試。面試官是一位經驗豐富的技術專家&#xff0c;他將通過多輪提…

使用vue2開發一個醫療預約掛號平臺-前端靜態網站項目練習

對于后端開發的我&#xff0c;最近一直在學習前端開發&#xff0c;除了要學習一些前端的基礎知識外&#xff0c;肯定少不了一些前端項目練習&#xff0c;就通過前端的編程知識 就簡單做一個醫療預約掛號前端靜態頁面。這個網站主要是使用了vue2 的相關技術實現的。 主要實現了這…

MongoDB(docker版)備份還原

docker啟動MongoDB docker run -d -p 27017:27017 --name my-mongo -v /mongodb/db:/data/db mongo備份MongoDB 使用mongodump備份數據庫時&#xff0c;默認會將備份數據保存在當前工作目錄下的dump文件夾中。 docker容器中默認備份在當前工作目錄&#xff0c;所以此處指定當…

zkPass案例實戰之合約篇

目錄 一、contracts/contracts/ProofVerifier.sol 1. License 和 Solidity 版本 2. 導入依賴 3. 合約聲明和默認分配器地址 4. 驗證證明 5. 驗證分配器簽名 6. 驗證驗證者簽名 7. 簽名前綴處理 8. 簽名恢復 總結 二、contracts/contracts/SampleAttestation.sol 1. …

ElasticSearch:高并發場景下如何保證讀寫一致性?

在Elasticsearch高并發場景下&#xff0c;可以通過以下多種方式來保證讀寫一致性&#xff1a; 等待主分片和副本分片都確認&#xff08;類似半同步機制&#xff09; 設置consistency參數&#xff1a;在寫操作時&#xff0c;可以設置consistency參數來控制寫操作的一致性級別。…

8、constexpr if、inline、類模版參數推導、lambda的this捕獲、初始化列表、namespace---c++17

一、constexpr if&#xff1a;編譯時條件分支 作用&#xff1a;在模板編程中&#xff0c;根據條件在編譯時選擇不同的代碼路徑&#xff0c;無需特化版本或復雜SFINAE技巧[替代SFINAE]。[SFINAE將在模版元編程再講。下個月了。] 注意&#xff1a;默認使用了隱式inline 基本語法…

【Java設計模式及實踐學習-第4章節-結構型模式】

第4章節-結構型模式 筆記記錄 1. 適配器模式2. 代理模式3. 裝飾器模式4. 橋接模式5. 組合模式6. 外觀模式7. 享元模式8. 總結 1. 適配器模式 2. 代理模式 3. 裝飾器模式 4. 橋接模式 5. 組合模式 6. 外觀模式 7. 享元模式 Java語言中的String字符串就使用了享元模式&…

unity基礎自學2.3:移動和抓握物品

文章目錄 前言&#xff1a;1、基礎配置①XR Interaction Toolkit②創建一個XR場景③示例文件實現④ 一鍵配置&#xff08;PICO Building Blocks&#xff09; 2、射線移動物品和抓握物品方法一&#xff1a;Grab Interactable方法二&#xff1a;prefab 3、Box Collider的作用與使…

pytest基礎-new

規范 1、首先創建 py 文件命名以 test_ 開始或者以 _test 結尾 2、若是新建類&#xff0c;測試類需要以 Test_開頭 3、測試用例&#xff08;方法&#xff09;需要以 test_開頭 assert 斷言 assert xx&#xff1a;判斷 xx 為真 assert not xx&#xff1a;判斷 xx 不為真 asse…

【華為OD機試真題】232、統計射擊比賽成績 | 機試真題+思路參考+代碼分析(C++)

題目描述 給定一個射擊比賽成績單,包含多個選手若干次射擊的成績分數,請對每個選手按其最高3個分數之和進行降序排名,輸出降序排 名后的選手ID序列 條件如下: 1.一個選手可以有多個射擊成績的分數,且次序不固定 2.如果一個選手成績少于3個,則認為選手的所有成績無效,排名…

?Unity 開發 | 如何通過 NTP 網絡時間實現精準的跨平臺時間同步【附完整源碼 + UI 模塊 + 偏差分析】

&#x1f3ae; 項目實戰 | 實現一套精確、可視化的游戲時間同步機制&#xff0c;讓你的多人在線游戲擺脫“時間不一致”噩夢&#xff01; 效果如圖&#xff1a; &#x1f4cc; 一、前言&#xff1a;為什么不能只信本地時間&#xff1f; 在 Unity 游戲開發中&#xff0c;時間幾…