• 個(gè)人博客：https://javaniuniu.com/
• 難度：簡(jiǎn)單
• 本題涉及算法： 二分查找
• 思路： 二分查找 暴力 目標(biāo)值插入數(shù)組
• 類似題型：

題目 35. 搜索插入位置

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

你可以假設(shè)數(shù)組中無(wú)重復(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

方法一 二分查找

• 復(fù)雜度分析：
  • 時(shí)間復(fù)雜度 ，這里 是數(shù)組的長(zhǎng)度，每一次都將問(wèn)題的規(guī)模縮減為原來(lái)的一半，因此時(shí)間復(fù)雜度是對(duì)數(shù)級(jí)別的
  • 空間復(fù)雜度

python

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left , right = 0, len(nums)
        while left < right:
            mid = left + (right - left)/2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

方法二 暴力遍歷

• 復(fù)雜度分析：
  • 時(shí)間復(fù)雜度 ，這里 是數(shù)組的長(zhǎng)度，最差情況下遍歷 目標(biāo)值>數(shù)組最后一個(gè)值
  • 空間復(fù)雜度

python

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        if nums[-1] < target:
            return len(nums)
        for i in range(len(nums)):
            if nums[i] >= target:
                return i

java

class Solution {
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        int ans = 0;
        if (len == 0){
            return 0;
        }
        if (nums[len-1] < target) {
            return len;
        }

        for (int i = 0;i<len;i++) {
            if (nums[i] >= target) {
                ans = i;
                break;
            }
        }
        return ans;
    }
}

方法三 目標(biāo)值插入數(shù)組后在查找對(duì)于位置（提供了一個(gè)新思路）

• 解題思路：
  • 目標(biāo)值插入數(shù)組中
  • 排序后在查詢對(duì)于目標(biāo)值的位置
• 復(fù)雜度分析：
  • 時(shí)間復(fù)雜度 ，這里 是數(shù)組的長(zhǎng)度，最差情況下遍歷 目標(biāo)值>數(shù)組最后一個(gè)值
  • 空間復(fù)雜度

python

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # 不管這個(gè)數(shù)在不在里面，直接append
        nums.append(target)
        # 然后再排序
        nums.sort()
        # 最后返回查找的index
        return nums.index(target)