二分查找學習:優雅的二分查找——“Leetcode 35. 搜索插入位置”

例題

給定一個排序數組和一個目標值,在數組中找到目標值,并返回其索引。如果目標值不存在于數組中,返回它將會被按順序插入的位置。

請必須使用時間復雜度為 O(log n) 的算法。

示例 1:
輸入: nums = [1,3,5,6], target = 5
輸出: 2

示例 2:
輸入: nums = [1,3,5,6], target = 2
輸出: 1

示例 3:
輸入: nums = [1,3,5,6], target = 7
輸出: 4

思路

典型的二分查找問題,但是怎么樣將這個代碼寫得優雅?怎樣將問題思考得簡潔,能解決問題并且沒有邊界條件得疏漏?怎么樣再每次遇到二分查找問題時都能以一種思路優雅而正確地寫出代碼?

下面是這道題的代碼:

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:l = 0r = len(nums)-1while(l <= r):mid = (l+r) // 2if(nums[mid] < target):l = mid + 1else:r = mid - 1return l

非常優雅,無需判定任何邊界條件。有多種方法可以證明這個方法的正確性,有的過于繁瑣,以至于在每次編寫二分查找代碼時,都要進行繁復的思考,花費時間且可能出錯。

下面是一種優雅的思考方法,我稱之為:收斂+條件:

  1. 每一次循環,必然導致端點移動,因此不會出現死循環問題,也就是必定有解
  2. 本題是找出第一個≥target的元素,l只會向右移動,初始l=0,且每次l都在<target的情況下。向右移動一個元素,因此l肯定不會突破約束
  3. 退出時的狀態肯定是,l指向了第一個≥target的元素。
    具體來說,l不可能指向后幾個≥target的元素,因為l只會每次l都在<target的情況下。向右移動一個元素,一旦l≥target,循環存在,r≥l,此時只會改變r的位置。

由于上面推論3,代碼還可增加一行優化成:

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:l = 0r = len(nums)-1while(l <= r):mid = (l+r) // 2if(nums[mid] < target):l = mid + 1else:r = mid - 1if(l>=len(nums) or nums[l] >= target): return lreturn l

需要注意的是,以上代碼返回的索引可能會超出原有的數組邊界,在以后活用此方法時,應該注意到這個問題。

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

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

相關文章

怎么花草識別?方法有三種!

怎么花草識別&#xff1f;在這個五彩斑斕的世界里&#xff0c;花草是我們生活中不可或缺的一部分。它們點綴著我們的環境&#xff0c;為我們帶來無盡的美麗與驚喜。然而&#xff0c;面對眾多的花草種類&#xff0c;你是否曾感到困惑和迷茫&#xff0c;不知道如何識別它們&#…

VIO System 丨適用于控制器開發前期的測試系統

VIO綜述 嵌入式軟件的HIL測試需要復雜的測試系統及完整的ECU硬件&#xff0c;這導致通常只能在開發流程的后期階段進行測試。全新推出的低成本解決方案VIO System&#xff0c;使得在開發前期不僅可以進行總線通訊測試&#xff0c;也可以同時進行I/O信號測試。 該系統旨在通過…

用 Vim 打造舒適高效的編程體驗

作為程序員,Vim 無疑是最常使用的編輯器之一。它之所以如此受歡迎,得益于其強大的功能和高度可定制的特性。今天,讓我帶大家一起探索如何通過簡單的 .vimrc 配置,打造一個個性化的 Vim 編程環境。 啟用語法高亮 我們首先要確保 Vim 能夠正確地識別和高亮代碼語法。只需在 .vi…

LabVIEW版本控制

LabVIEW作為一種流行的圖形化編程環境&#xff0c;在軟件開發中廣泛應用。有效地管理版本控制對于確保軟件的可靠性和可維護性至關重要。LabVIEW提供了多種方式來管理VI和應用程序的修訂歷史&#xff0c;以滿足不同規模和復雜度的項目需求。 LabVIEW中的VI修訂歷史 LabVIEW內置…

docker安裝Mysql5.7版本

首先Linux系統已經安裝好了docker應用。 1.搜索鏡像 docker search mysql 2.拉取5.7的鏡像 總之,選starts最多的那個就對了。 docker pull mysql:5.7 ~ docker pull mysql:5.7 5.7: Pulling from library/mysql fc7181108d40: Downloading [============> …

mysql創建數據表----centos7.9

mysql創建數據表 查看存在的表 show tables;我這里還未創建任何表所以是這樣的 如有是這樣 若沒有表需要先創建一個表 CREATE DATABASE tb_your_name&#xff1b;創建字段及屬性 CREATE TABLE tb_laws_regulations (id INT AUTO_INCREMENT PRIMARY KEY, -- 文件唯…

柯橋外貿俄語哪里可以學,零基礎俄語培訓

Де?лать 做 из му?хи 從蒼蠅 слона? 大象 我覺得漢語里有一個很合適的詞來形容&#xff1a; Де?лать из му?хи слона? 就是 小題大做&#xff0c;本來是一件很小的事&#xff0c;卻把它形容成天大的事一樣 Хвтит де?…

【UE5.1 角色練習】10-物體抬升、拋出技能 - part2

目錄 前言 效果 步驟 一、讓物體緩慢的飛向手掌 二、向著鼠標方向發射物體 前言 在上一篇&#xff08;【UE5.1 角色練習】08-物體抬升、拋出技能 - part1&#xff09;的基礎上繼續完成角色將物體吸向手掌&#xff0c;然后通過鼠標點擊的方向來發射物體的功能。 效果 步驟…

c#實現BPM系統網絡傳輸接口,http協議,post

BPM通過http協議實現網絡傳輸&#xff0c;語言使用.net(c#)&#xff0c;在這里只提供一個接口&#xff0c;具體代碼如下,請參照&#xff1a; public string MakeRequest(string parameters) { ServicePointManager.ServerCertificateValidationCallback new Syst…

代碼隨想錄算法訓練營第三十二 | ● 122.買賣股票的最佳時機II ● 55. 跳躍游戲 ● 45.跳躍游戲II

122.買賣股票的最佳時機II 講解鏈接&#xff1a;https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html 簡單思路&#xff1a;逐個計算連續兩天的股票差值&#xff0c;sum初始為零&…

Spring Task 定時任務

文章目錄 Spring Task 定時任務pom 包配置啟動類開啟定時創建定時任務實現類定時任務 1:定時任務 2: 參數說明fixedRate 說明cron 說明 并行任務 Spring Task 定時任務 在項目開發中&#xff0c;經常需要定時任務來幫助我們來做一些內容&#xff0c;比如定時派息、跑批對賬、業…

【并查集】專題練習

題目列表 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn) 模板 836. 合并集合 - AcWing題庫 #include<bits/stdc.h> using lllong long; //#define int ll const int N1e510,mod1e97; int n,m; int p[N],sz[N]; int find(int a) {if(p[a]!a) p[a]find(p[a]);return p[a…

第十八講:聯合和枚舉

第十八講&#xff1a;聯合和枚舉 1.聯合體&#xff08;共用體&#xff09;1.1聯合體的聲明1.2聯合體大小的計算1.3聯合體的特點1.4聯合體的使用1.4.1聯合體的直接使用1.4.2聯合體直接使用的優化方法1.4.3聯合體成員中含有數組的使用1.4.4使用聯合體判斷當前機器是大端排序&…

K8s(Kubernetes)常用命令

大家好&#xff0c;當談及容器編排工具時&#xff0c;Kubernetes&#xff08;常簡稱為K8s&#xff09;無疑是當今最受歡迎和廣泛使用的解決方案之一。作為一個開源的容器編排平臺&#xff0c;Kubernetes 提供了豐富的功能&#xff0c;可以幫助開發人員和運維團隊管理、部署和擴…

電商分析@電商數據與運營優化

電商數據分析與運營優化是指通過對電商平臺的各種數據進行深入分析&#xff0c;以發現潛在的問題和機會&#xff0c;并采取相應的優化措施&#xff0c;提高電商運營效率和盈利能力。 首先&#xff0c;電商數據分析需要收集和整理各類數據&#xff0c;包括銷售數據、用戶數據、流…

大宋咨詢(深圳車主滿意度調查)如何開展汽車展會觀眾滿意度問卷調查

汽車展覽是由政府機構、專業協會或主流媒體等組織,在專業展館或會場中心進行的汽車產品展示展銷會或汽車行業經貿交易會、博覽會等活動。汽車展覽通過對汽車工藝的呈現與汽車產品的廣告,為消費者提供汽車制造工業與汽車產品的發展動向。同時,汽車廠商可通過汽車展覽對外宣傳產品…

實戰16:基于apriori關聯挖掘FP-growth算法挖掘關聯規則的手機銷售分析-代碼+數據

直接看視頻演示: 基于apriori關聯挖掘關聯規則的手機銷售分析與優化策略 直接看結果: 這是數據展示: 挖掘結果展示: 數據分析展示:

利用WK2168實現串口服務器

ESP32 SPI與WK2168實現串口服務器 概述系統組成代碼概述 一些老設備通過RS485采集數據,如果在一個系統中采用幾個RS485設備可能是一個不錯的選擇,但要是使用46個RS485數據采集設備為一個PLC提供外部數據,系統的性能就很難有保障了。通過一個串口服務器實現看來是一個好的選…

智慧校園有哪些特征

隨著科技的飛速進步&#xff0c;教育領域正經歷著一場深刻的變革。智慧校園&#xff0c;作為這場變革的前沿代表&#xff0c;正在逐步重塑我們的教育理念和實踐方式。它不僅僅是一個概念&#xff0c;而是一個集成了物聯網、大數據、人工智能等先進技術的綜合生態系統&#xff0…

SpringBoot源碼(自動裝配、內嵌Tomcat)

文章目錄 依賴管理pom依賴管理Web依賴自定義starter 一、WebMvcAutoConfiguration1.1 Filter1.2 Interceptor 二、源碼解析2.1 SpringApplication2.1.1 構造方法1、填充webApplicationType2、自動裝配Initializers3、自動裝配Listeners 2.1.2 run(args) 2.2 SpringApplicationR…