【Java算法】二分查找 下

????🔥個人主頁:?中草藥

🔥專欄:【算法工作坊】算法實戰揭秘


一.山脈數組的峰頂索引

題目鏈接:852.山脈數組的峰頂

?

算法原理

????????這段代碼實現了一個查找山峰數組中峰值索引的算法。山峰數組是一個先遞增后遞減的數組,即存在一個索引 i 使得對于所有的 j < i,有 arr[j] < arr[j + 1],且對于所有的 k > i,有 arr[k] > arr[k - 1]。這個索引 i 就是峰值的索引。

????????算法使用了二分查找(Binary Search)的方法來尋找峰值索引。其核心思想是在數組中尋找拐點(即峰值),在該點左側的值小于右側的值,在右側則相反。由于數組是先升后降的,這個拐點就是我們所要找的峰值。

具體分析如下:

  1. 初始化兩個指針 leftright,分別指向數組的第二個元素和倒數第二個元素。這是因為數組的第一個和最后一個元素不可能是峰值。

  2. while 循環中,計算中間位置 mid。這里使用 (left + (right - left + 1)) / 2 而不是常見的 (left + right) / 2 來避免可能的整數溢出,并確保 mid 總是指向 leftright 之間的元素,包括邊界上的元素。

  3. 如果 arr[mid] 大于 arr[mid - 1],說明 mid 可能是峰值或者峰值在 mid 的右邊,因此將 left 更新為 mid

  4. 否則,如果 arr[mid] 小于或等于 arr[mid - 1],說明峰值在 mid 的左邊,因此將 right 更新為 mid - 1

  5. leftright 相遇時,循環結束,此時 left 指向的位置就是峰值的索引。

這種算法的時間復雜度是 O(log n),其中 n 是數組的長度,因為每次迭代都將搜索范圍減半。這比線性搜索的 O(n) 時間復雜度要高效得多。

代碼

 public int peakIndexInMountainArray(int[] arr) {int left=1,right=arr.length-2;while(left<right){int mid=left+(right-left+1)/2;if(arr[mid]>arr[mid-1]){left=mid;}else{right=mid-1;}}return left;}

舉例?

測試用例 arr = [0,10,5,2]

首先,初始化 left = 1right = arr.length - 2 = 2

接下來,我們進入 while 循環:

  1. 第一次循環:

    • left = 1,?right = 2
    • 計算?mid = left + (right - left + 1) / 2 = 1 + (2 - 1 + 1) / 2 = 2
    • 檢查?arr[mid]?是否大于?arr[mid - 1],也就是檢查?arr[2]?是否大于?arr[1]。由于?arr[2] = 5?并不大于?arr[1] = 10,條件不滿足。
    • 所以,我們將?right?更新為?mid - 1,即?right = 1
  2. 這時,leftright 都指向同一個位置 1,循環條件 left < right 不再滿足,循環結束。

最后,返回 left 的值,即 1。這意味著數組中的峰值位于索引 1 上,這與給定數組 [0, 10, 5, 2] 的實際情況相吻合,因為最大值 10 確實位于索引 1

所以,這段代碼正確地找到了山峰數組的峰值索引。

?二.尋找峰值

題目鏈接:162.尋找峰值

?

算法原理

????????同樣使用了二分查找(Binary Search)算法來找到所謂的“峰值元素”。峰值元素定義為一個元素,它嚴格大于它的鄰居。注意,數組可以是未排序的,并且數組的兩端被認為是鄰居元素的“虛擬”較小值,這樣數組的起始元素和末尾元素也可以成為峰值元素。

算法的步驟如下:

  1. 初始化兩個指針 leftright,分別指向數組的起始位置 0 和終止位置 nums.length - 1

  2. 進入 while 循環,只要 left 小于 right,表示搜索區間內還有多個元素需要考慮。

  3. 在循環內部,計算中間位置 mid。這里使用 (left + (right - left) / 2) 來避免整數溢出,并確保 mid 總是落在 leftright 之間。

  4. 比較 nums[mid]nums[mid + 1] 的大小。如果 nums[mid] 小于 nums[mid + 1],那么峰值一定不在 mid 及其左側,因為從 midmid + 1 數組是上升的。這時,將 left 更新為 mid + 1

  5. 否則,如果 nums[mid] 大于或等于 nums[mid + 1],那么峰值可能在 mid 或者其左側。這時,將 right 更新為 mid

  6. leftright 相遇時,循環結束,此時 left 指向的位置就是峰值元素的索引。這是因為當 left == right 時,它們共同指向的元素必定是峰值,因為在之前的迭代中,我們總是排除了較小的鄰居元素所在的那一邊。

這段代碼的時間復雜度同樣是 O(log n),其中 n 是數組的長度,因為每次迭代都將搜索范圍減半,這使得算法非常高效。

代碼

public int findPeakElement(int[] nums) {int left=0,right=nums.length-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]<nums[mid+1]){left=mid+1;}else{right=mid;}}return left;}

舉例?

測試用例 [1,2,1,3,5,6,4]

我們開始分析:

  1. 初始化 left = 0right = nums.length - 1 = 6

  2. 第一次循環:

    • mid = left + (right - left) / 2 = 0 + (6 - 0) / 2 = 3
    • 檢查?nums[mid]?和?nums[mid + 1],即?nums[3]?和?nums[4],比較?3?和?5
    • 因為?nums[3]?小于?nums[4],所以更新?left?為?mid + 1,即?left = 4
  3. 第二次循環:

    • 此時?left = 4?和?right = 6
    • mid = left + (right - left) / 2 = 4 + (6 - 4) / 2 = 5
    • 檢查?nums[mid]?和?nums[mid + 1],即?nums[5]?和?nums[6],比較?6?和?4
    • 因為?nums[5]?不小于?nums[6],所以更新?right?為?mid,即?right = 5
  4. 第三次循環:

    • 現在?left = 4?和?right = 5
    • mid = left + (right - left) / 2 = 4 + (5 - 4) / 2 = 4
    • 檢查?nums[mid]?和?nums[mid + 1],即?nums[4]?和?nums[5],比較?5?和?6
    • 因為?nums[4]?小于?nums[5],所以更新?left?為?mid + 1,即?left = 5
  5. 第四次循環:

    • 此時?left = 5?和?right = 5
    • 因為?left?等于?rightwhile?循環的條件不再滿足,循環結束。

最終,函數返回 left 的值,即 5。這表明數組 [1, 2, 1, 3, 5, 6, 4] 中的一個峰值元素位于索引 5,其值為 6。值得注意的是,根據題目的定義,可能有多個峰值元素,而算法保證返回的是其中一個。在這個例子中,索引 1 (nums[1] = 2) 和索引 5 (nums[5] = 6) 都是合法的峰值元素。

三.尋找旋轉排序數組的最小值

題目鏈接:153.尋找旋轉排序數組的最小值

??

算法原理

????????這段代碼實現了一個算法,用于在一個旋轉排序數組中找到最小元素。旋轉排序數組指的是原本有序的數組經過若干次旋轉得到的結果。例如,數組 [1, 2, 3, 4, 5] 經過旋轉可能變成 [3, 4, 5, 1, 2]

????????算法的原理基于二分查找(Binary Search),但是針對旋轉排序數組進行了調整。關鍵在于利用旋轉特性來縮小搜索范圍。旋轉數組的最小元素位于旋轉點之后,旋轉點之前的子數組是遞增的,旋轉點之后的子數組也是遞增的,但整個數組的順序被打亂。

算法步驟如下:

  1. 初始化 leftright 分別指向數組的起始和末尾位置。

  2. 獲取數組最后一個元素 x 作為基準值。這是因為在旋轉數組中,最后一個元素通常是未旋轉前數組的最后一個元素,或者是旋轉后新數組的最大值。

  3. 進入 while 循環,只要 left < right,就說明搜索空間大于1個元素。

  4. 計算中間位置 mid,使用 (left + (right - left) / 2) 來避免整數溢出問題。

  5. 比較 nums[mid]x 的大小:

    • 如果?nums[mid] > x,說明?mid?位于旋轉點的左側遞增子數組中,最小值只能在?mid?右側的子數組中,因此更新?left?為?mid + 1
    • 否則,nums[mid] <= x,說明?mid?位于旋轉點的右側遞增子數組中,或者正好位于旋轉點上,最小值可能在?mid?或者左側子數組中,因此更新?right?為?mid
  6. leftright 相遇時,循環結束,此時 left 指向的位置就是最小元素的索引,返回 nums[left] 即可得到最小值。

此算法的時間復雜度為 O(log n),其中 n 是數組的長度,因為它在每一步都有效地將搜索空間減半。這使得算法在處理大數據量時非常高效。

代碼

 public int findMin(int[] nums) {int left=0,right=nums.length-1;int x=nums[right];while(left<right){int mid=left+(right-left)/2;if(nums[mid]>x){left=mid+1;}else{right=mid;}}return nums[left];}

舉例?

測試用例 nums = [4,5,6,7,0,1,2]

我們開始逐步分析:

  1. 初始化?left = 0?和?right = nums.length - 1 = 6
  2. 設置?x = nums[right] = nums[6] = 2

第一次循環:

  • mid = left + (right - left) / 2 = 0 + (6 - 0) / 2 = 3
  • 檢查?nums[mid]?和?x,即?nums[3]?和?2,比較?7?和?2
  • 因為?nums[mid]?大于?x,更新?left?為?mid + 1,即?left = 4

第二次循環:

  • 此時?left = 4?和?right = 6
  • mid = left + (right - left) / 2 = 4 + (6 - 4) / 2 = 5
  • 檢查?nums[mid]?和?x,即?nums[5]?和?2,比較?1?和?2
  • 因為?nums[mid]?不大于?x,更新?right?為?mid,即?right = 5

第三次循環:

  • 此時?left = 4?和?right = 5
  • mid = left + (right - left) / 2 = 4 + (5 - 4) / 2 = 4
  • 檢查?nums[mid]?和?x,即?nums[4]?和?2,比較?0?和?2
  • 因為?nums[mid]?不大于?x,更新?right?為?mid,即?right = 4

第四次循環:

  • 現在?left = 4?和?right = 4
  • while?循環的條件?left < right?不再滿足,循環結束。

最終,函數返回 nums[left] 的值,即 nums[4],結果為 0

這表明數組 [4, 5, 6, 7, 0, 1, 2] 中的最小元素為 0,位于索引 4。此算法成功找到了旋轉排序數組中的最小元素。

四.LCR 173.點名?

題目鏈接:LCR 173.點名

?

算法原理

  1. 初始化兩個指針 leftright,分別指向數組的起始位置 0 和終止位置 records.length - 1

  2. 使用 while 循環,只要 left < right,意味著數組中還可能存在不匹配的情況。

  3. 計算中間位置 mid,使用 (left + (right - left) / 2) 來避免整數溢出。

  4. 檢查 mid 位置的元素是否等于 mid

    • 如果?records[mid]?等于?mid,這意味著?mid?位置的值與索引匹配,因此缺失的元素可能在?mid?的右側。更新?left?為?mid + 1
    • 否則,如果?records[mid]?不等于?mid,這可能是由于缺失的元素在?mid?的位置應該出現,但實際沒有出現。因此,更新?right?為?mid,繼續在左側查找。
  5. leftright 相遇時,循環結束。此時,left 指向的位置要么是缺失元素應該出現的位置,要么緊隨其后。

  6. 最后,檢查 left 位置的元素是否等于 left

    • 如果?left?位置的元素等于?left,這意味著?left?位置的元素沒有缺失,因此缺失的元素應該是?left + 1
    • 否則,left?位置的元素小于?left,這意味著?left?位置的元素是缺失的,因此缺失的元素就是?left

時間復雜度為 O(log n),其中 n 是數組的長度,因為算法使用了二分查找,每次迭代都將搜索范圍減半。

這種算法特別適用于數據量大、有序或部分有序的數組中查找缺失的元素,效率遠高于線性查找。

代碼

public int takeAttendance(int[] records) {int left=0,right=records.length-1;while(left<right){int mid=left+(right-left)/2;if(mid==records[mid]){left=mid+1;}else{right=mid;}}//判斷特殊情況,如[0,1,2,3,4,5]此時缺少的值應該是6if(left==records[left]){return left+1;}return left;}

舉例?

測試用例 records = [0, 1, 2, 3, 4, 5, 6, 8]

我們開始逐步分析:

  1. 初始化?left = 0?和?right = records.length - 1 = 7

第一次循環:

  • mid = left + (right - left) / 2 = 0 + (7 - 0) / 2 = 3
  • 檢查?records[mid]?和?mid,即?records[3]?和?3,比較?3?和?3
  • 因為?records[mid]?等于?mid,更新?left?為?mid + 1,即?left = 4

第二次循環:

  • 此時?left = 4?和?right = 7
  • mid = left + (right - left) / 2 = 4 + (7 - 4) / 2 = 5
  • 檢查?records[mid]?和?mid,即?records[5]?和?5,比較?5?和?5
  • 因為?records[mid]?等于?mid,更新?left?為?mid + 1,即?left = 6

第三次循環:

  • 此時?left = 6?和?right = 7
  • mid = left + (right - left) / 2 = 6 + (7 - 6) / 2 = 6
  • 檢查?records[mid]?和?mid,即?records[6]?和?6,比較?6?和?6
  • 因為?records[mid]?等于?mid,更新?left?為?mid + 1,即?left = 7

第四次循環:

  • 現在?left = 7?和?right = 7
  • while?循環的條件?left < right?不再滿足,循環結束。

退出循環后:

  • 檢查?left?位置的元素是否等于?left,即?records[7]?和?7,比較?8?和?7
  • 因為?records[left]?不等于?left,直接返回?left?的值,即?7

然而,根據代碼邏輯,如果 left 位置的元素等于 left,我們應該返回 left + 1;否則,返回 left。在本例中,left 已經等于數組的長度,且 records[left] 實際上超出了正常的序列,因此正確結果應為 left 的值,即 7,這表明缺失的元素是 7

因此,這段代碼正確地找到了測試用例 [0, 1, 2, 3, 4, 5, 6, 8] 中缺失的元素,即 7


🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀

以上,就是本期的全部內容啦,若有錯誤疏忽希望各位大佬及時指出💐

? 制作不易,希望能對各位提供微小的幫助,可否留下你免費的贊呢🌸

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

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

相關文章

玩具營銷是如何拿捏成年人錢包?

好像現在的成年人逐漸熱衷于偏向年輕化&#xff0c;問問題會好奇“尊嘟假嘟”&#xff0c;飯量上的“兒童套餐”&#xff0c;娃娃機前排長隊......而最突出的莫過于各類各式的玩具不斷收割當代年輕人&#xff0c;除去常給大朋友們小朋友們送去玩具福利的“麥、肯”雙門&#xf…

激光干涉儀可以完成哪些測量:全面應用解析

在高端制造領域&#xff0c;精度是衡量產品質量的關鍵指標之一。激光干涉儀作為一項高精度測量技術&#xff0c;其應用廣泛&#xff0c;對于提升產品制造精度具有重要意義。 線性測量&#xff1a;精確定位的基礎 激光干涉儀采用邁克爾遜干涉原理&#xff0c;實現線性測量。該…

AlphaGo 的傳奇故事

文章目錄 一、說明二、AlphaGo 傳奇&#xff08;一&#xff09;&#xff1a;游戲規則三、AlphaGo 傳奇(二)&#xff1a;它是如何運作的&#xff1f;四、AlphaGo 傳奇&#xff08;三&#xff09;&#xff1a;史詩般的戰斗和人工智能的未來 一、說明 1997 年&#xff0c;IBM 的“…

卷積神經網絡之ResNet50遷移學習

數據準備 下載狗與狼分類數據集&#xff0c;數據來自ImageNet&#xff0c;每個分類有大約120張訓練圖像與30張驗證圖像。使用download接口下載數據集&#xff0c;并自動解壓到當前目錄。 全是小狗的圖片 另一邊全是狼的圖片 加載數據集 狼狗數據集提取自ImageNet分類數據集&a…

2-3個月的幼貓能吃主食凍干嗎?第一次吃哪款主食凍干比較好

2-3個月的幼貓能吃凍干嗎&#xff1f;一般來說&#xff0c;幼貓在2-3個月左右的離乳期就可以吃凍干了。需要注意的&#xff0c;一個是要認準主食凍干&#xff0c;零食凍干會讓貓貓從小就挑食&#xff0c;以后就更不好糾正了。而且離乳期的貓貓沒有了母乳的保護&#xff0c;免疫…

Open3D 點對面的ICP算法配準(精配準)

目錄 一、概述 1.1核心思想 1.2實現步驟 二、代碼實現 2.1關鍵函數 2.2完整代碼 三、實現效果 3.1原始點云 3.2配準后點云 3.3計算數據 一、概述 基于點對面的ICP&#xff08;Iterative Closest Point&#xff09;配準算法是ICP的一種變體&#xff0c;它通過最小化源…

【Ty CLI】一個開箱即用的前端腳手架

目錄 資源鏈接基礎命令模板創建命令幫助選擇模板開始創建開發模板 開發背景npm 發布流程問題記錄模板創建超時 更新日志 資源鏈接 文檔&#xff1a;https://ty.cli.vrteam.top/ 源碼&#xff1a;https://github.com/bosombaby/ty-cli 基礎命令 1. npm 全局安裝 npm i ty-cli…

Zabbix Sia Zabbix 邏輯漏洞(CVE-2022-23134)

前言 CVE-2022-23134是一個中等嚴重度的漏洞&#xff0c;影響Zabbix Web前端。這個漏洞允許未經身份驗證的用戶訪問setup.php文件的某些步驟&#xff0c;這些步驟通常只對超級管理員開放。利用這個漏洞&#xff0c;攻擊者可以通過跳過某些步驟來重新配置Zabbix前端&#xff0c…

gazebo仿真環境中加入livox mid360

https://github.com/Livox-SDK/livox_laser_simulation 功能包適用于ubuntu18.04 gazebo9的可以直接編譯運行。在ubutun20.04 的系統下gazebo是11版本,需要做一些修改 CMakeLists.txt文件中的 add_compile_options(-std=c++11) 改為 add_compile_options(-std=c++17)fatal er…

二一、搭建自已的語言大模型

1. 配置langchain環境 使用conda創建一個虛擬環境,基于 Python3.10,并在虛擬環境內安裝項目的依賴。注意,大模型對gpu有一定的要求,否則速度會奇慢無比。 conda create -n langchain python=3.10 conda env list conda activate langchain # 拉取倉庫 $ git clone ht…

Redis-Jedis連接池\RedisTemplate\StringRedisTemplate

Redis-Jedis連接池\RedisTemplate\StringRedisTemplate 1. Jedis連接池1.1 通過工具類1.1.1 連接池&#xff1a;JedisConnectionFactory&#xff1a;1.1.2 test&#xff1a;&#xff08;代碼其實只有連接池那里改變了&#xff09; 2. SpringDataRedis&#xff08;lettuce&#…

終于弄明白了什么是EI!

EI是Engineering Index的縮寫&#xff0c;中文意為“工程索引”&#xff0c;是由美國工程信息公司(Engineering Information, Inc.)編輯出版的著名檢索工具。它始創于1884年&#xff0c;擁有超過一個世紀的歷史&#xff0c;是全球工程界最權威的文獻檢索系統之一。EI雖然名為“…

十五、小型電腦沒有數字鍵及insert,怎么解決IDEA快速插入getset構造這些方法

&#x1f33b;&#x1f33b;目錄 一、小型電腦沒有數字鍵及insert&#xff0c;怎么解決IDEA快速插入getset構造這些方法 一、小型電腦沒有數字鍵及insert&#xff0c;怎么解決IDEA快速插入getset構造這些方法 解決&#xff1a; 1.winR打開搜索 2.osk回車 屏幕就出現了這樣的一…

CC7利用鏈分析

分析版本 Commons Collections 3.2.1 JDK 8u65 環境配置參考JAVA安全初探(三):CC1鏈全分析 分析過程 CC7,6,5都是在CC1 LazyMap利用鏈(引用)的基礎上。 只是進入到LazyMap鏈的入口鏈不同。 CC7這個鏈有點繞&#xff0c;下面順著分析一下利用鏈。 入口類是Hashtable&…

前端入門知識分享:如何在HTML或CSS文件中引用CSS文件。

閱讀提示&#xff1a;本文僅僅僅適用于剛剛接觸HTML和CSS的小白從業者&#xff0c;新人愛好者。自覺身份不符的老鳥們&#xff0c;盡快繞行吧&#xff01; 什么是CSS&#xff1f;什么是CSS文件。 CSS&#xff0c;全稱為Cascading Style Sheets&#xff08;層疊樣式表&#xff…

分布式IO模塊軟件配置

組態接口模塊 1、打開網絡視圖 2、拖拽出ET200SP 3、雙擊ET200SP的圖片&#xff0c;進入從站配置 總線適配器的組態更換 關于IO地址分配&#xff0c;需要建立好子網通信后&#xff0c;在主機上配置。 可以看到IP 和設備名 設備與控制器的Profinet連接 先找到設備名稱再找…

HarmonyOS鴻蒙DevEco Studio無法連接本地模擬器

使用DevEcoStudio 5.0.3.403版本 發現無法選擇模擬器 解決方法&#xff1a; 1、打開模擬器 2、關閉DevEco Studio&#xff0c;&#xff08;不要關閉模擬器&#xff09; 3、重新打開DevEco Studio。

EXCEL VBA發郵件,實現自動化批量發送

EXCEL VBA發郵件&#xff0c;實現自動化批量發送 以GET方式上傳數據 Public Function uploadData_GET(ByVal url As String)Dim httpSet http CreateObject("Microsoft.XMLHTTP")http.Open "GET", url, Falsehttp.sendDebug.Print http.getAllResponseHea…

四道經典算法JAVA

1.爬樓地 爬20個臺階的爬法:f(19)f(18) 經典斐波拉契數列問題 public class demo4 {//爬樓梯問題public static void main(String[] args) {System.out.println(getSum(20));}public static int getSum(int n) {if (n 1)return 1;if (n 2)return 2;return getSum(n - 1) …

SpringBoot:SpringBoot中如何實現對Http接口進行監控

一、前言 Spring Boot Actuator是Spring Boot提供的一個模塊&#xff0c;用于監控和管理Spring Boot應用程序的運行時信息。它提供了一組監控端點&#xff08;endpoints&#xff09;&#xff0c;用于獲取應用程序的健康狀態、性能指標、配置信息等&#xff0c;并支持通過 HTTP …