溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下Leetcode如何搜索插入位置，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
input：[1, 3, 5, 6] 5out：2
input：[1, 3, 5, 6] 2out：1
input：[1, 3, 5, 6] 7out：4
本文由“壹伴編輯器”提供技術支持
第一次嘗試
數組：nums
目標值：target
從左到右遍歷數組，當nums[i]==target時，返回此刻的索引值i。當nums[i]>target時說明數組里面無目標值，并且target應該就插入到此刻的i處，故索引值也是i
nums[i] == target：返回索引值 i
nums[i] > target：也是返回索引值 i
速度并不快
優化算法——二分查找
曾經有個小品：奇志和大兵去看病，醫生讓他做了心肝脾肺腎的全面檢查，最后告訴他你就得了個感冒。雖然這是一個段子，但也映射出了一種分治思維
二分法思想（減治）：將【待搜索區域】劃分為【含目標區域】和【不含目標區域】，不斷的排除掉【不含目標區域】，最后剩下【含目標區域】
二分查找算法：
利用三個游標：left、right、mid不斷縮小區間
在使用二分查找算法時要思考2個問題
（1）返回 right 還是 left
（2）區域邊界如何設置
本文由“壹伴編輯器”提供技術支持
本題做法：
設置left、right、mid三個參數
循環條件為 while left<= right
區間的劃分方法：
（1）mid=target時：返回mid
（2）mid>target時：right = mid-1
（3）mid<target時：left = mid+1
此方法最后函數返回left（left始終對應target的位置即索引）
Python內置函數方法
對于python，這是代碼最簡潔的一個方法——利用內置函數
先判斷target是否存在于nums，存在直接返回index
若不在，則添加這個target進去nums，然后數組排序，返回target索引
本文由“壹伴編輯器”提供技術支持
其實也可以不判斷是否在數組中，反正出現重復，返回索引也是返回的第一個
二分法小結
三個游標：left、right、mid
要確定好區間劃分方法（left、right如何移動）
確定好函數最后返回的是哪個值（通過演算）
以上是“Leetcode如何搜索插入位置”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
