溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了如何使用java實現搜索插入位置，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。
給定一個排序數組和一個目標值，在數組中找到目標值，并返回其索引。如果目標值不存在于數組中，返回它將會被按順序插入的位置。
你可以假設數組中無重復元素。
示例 1:
輸入: [1,3,5,6], 5輸出: 2
示例 2:
輸入: [1,3,5,6], 2輸出: 1
示例 3:
輸入: [1,3,5,6], 7輸出: 4
示例 4:
輸入: [1,3,5,6], 0輸出: 0
標簽：二分查找
如果該題目暴力解決的話需要O(n)的時間復雜度，但是如果二分的話則可以降低到O(logn)的時間復雜度
整體思路和普通的二分查找幾乎沒有區別，先設定左側下標left和右側下標right，再計算中間下標mid
每次根據nums[mid]和target之間的大小進行判斷，相等則直接返回下標，nums[mid]<target則left右移，nums[mid]>target則right左移
查找結束如果沒有相等值則返回left，該值為插入位置
時間復雜度：O(logn)
二分查找的思路不難理解，但是邊界條件容易出錯，比如循環結束條件中left和right的關系，更新left和right位置時要不要加1減1。
下面給出兩個可以直接套用的模板，記住就好了，免除邊界條件出錯。
class Solution { public int searchInsert(int[] nums, int target) { int left = 0, right = nums.length - 1; // 注意 while(left <= right) { // 注意 int mid = (left + right) / 2; // 注意 if(nums[mid] == target) { // 注意 // 相關邏輯 } else if(nums[mid] < target) { left = mid + 1; // 注意 } else { right = mid - 1; // 注意 } } // 相關返回值 return 0; }}
或
class Solution { public int searchInsert(int[] nums, int target) { int left = 0, right = nums.length; // 注意 while(left < right) { // 注意 int mid = (left + right) / 2; // 注意 if(nums[mid] == target) { // 相關邏輯 } else if(nums[mid] < target) { left = mid + 1; // 注意 } else { right = mid; // 注意 } } // 相關返回值 return 0; }}
class Solution { public int searchInsert(int[] nums, int target) { int left = 0, right = nums.length - 1; while(left <= right) { int mid = (left + right) / 2; if(nums[mid] == target) { return mid; } else if(nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return left; }}
感謝你能夠認真閱讀完這篇文章，希望小編分享的“如何使用java實現搜索插入位置”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
