這篇文章主要介紹了如何使用java實現(xiàn)搜索插入位置，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。
成都創(chuàng)新互聯(lián)專注于洪澤企業(yè)網(wǎng)站建設(shè),成都響應(yīng)式網(wǎng)站建設(shè),商城開發(fā)。洪澤網(wǎng)站建設(shè)公司,為洪澤等地區(qū)提供建站服務(wù)。全流程按需規(guī)劃網(wǎng)站，專業(yè)設(shè)計，全程項目跟蹤，成都創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務(wù)
給定一個排序數(shù)組和一個目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會被按順序插入的位置。
你可以假設(shè)數(shù)組中無重復(fù)元素。
示例 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
標(biāo)簽：二分查找
如果該題目暴力解決的話需要O(n)的時間復(fù)雜度，但是如果二分的話則可以降低到O(logn)的時間復(fù)雜度
整體思路和普通的二分查找?guī)缀鯖]有區(qū)別，先設(shè)定左側(cè)下標(biāo)left和右側(cè)下標(biāo)right，再計算中間下標(biāo)mid
每次根據(jù)nums[mid]和target之間的大小進行判斷，相等則直接返回下標(biāo)，nums[mid]nums[mid]>target則right左移
查找結(jié)束如果沒有相等值則返回left，該值為插入位置
時間復(fù)雜度：O(logn)
二分查找的思路不難理解，但是邊界條件容易出錯，比如循環(huán)結(jié)束條件中l(wèi)eft和right的關(guān)系，更新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) { // 注意 // 相關(guān)邏輯 } else if(nums[mid] < target) { left = mid + 1; // 注意 } else { right = mid - 1; // 注意 } } // 相關(guān)返回值 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) { // 相關(guān)邏輯 } else if(nums[mid] < target) { left = mid + 1; // 注意 } else { right = mid; // 注意 } } // 相關(guān)返回值 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; }}
感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“如何使用java實現(xiàn)搜索插入位置”這篇文章對大家有幫助，同時也希望大家多多支持創(chuàng)新互聯(lián)，關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，更多相關(guān)知識等著你來學(xué)習(xí)!
