如何使用java實(shí)現(xiàn)搜索插入位置

發(fā)布時(shí)間：2022-01-17 11:43:38 來源：億速云閱讀：110 作者：小新欄目：大數(shù)據(jù)

這篇文章主要介紹了如何使用java實(shí)現(xiàn)搜索插入位置，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

題目描述

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。

你可以假設(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)的時(shí)間復(fù)雜度，但是如果二分的話則可以降低到O(logn)的時(shí)間復(fù)雜度
整體思路和普通的二分查找?guī)缀鯖]有區(qū)別，先設(shè)定左側(cè)下標(biāo)left和右側(cè)下標(biāo)right，再計(jì)算中間下標(biāo)mid
每次根據(jù)nums[mid]和target之間的大小進(jìn)行判斷，相等則直接返回下標(biāo)，nums[mid]<target則left右移，nums[mid]>target則right左移
查找結(jié)束如果沒有相等值則返回left，該值為插入位置
時(shí)間復(fù)雜度：O(logn)

二分查找的思路不難理解，但是邊界條件容易出錯(cuò)，比如循環(huán)結(jié)束條件中l(wèi)eft和right的關(guān)系，更新left和right位置時(shí)要不要加1減1。

下面給出兩個(gè)可以直接套用的模板，記住就好了，免除邊界條件出錯(cuò)。

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;    }}