☆打卡算法☆LeetCode 35、搜索插入位置 算法解析

一、题目

1、算法题目

“给定一个排序好的整数数组和一个目标值，在数组中找到目标值，返回其索引。如果目标值不存在数组中，就将目标值插入数组中按顺序的正确位置中。”

题目链接：

来源：力扣（LeetCode）

链接：35. 搜索插入位置 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1：
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2：
输入: nums = [1,3,5,6], target = 2
输出: 1

二、解题

1、思路分析

这个题的意思是找到排序数组中是否存在一个目标值，那么首先会想到的就是使用二分法在O(log n)的时间内找到是否存在目标值。

但这题还有额外的条件，就是数组中不存在目标值的话，返回按顺序插入的位置。

接着就是找到大于等于target的下标。

2、代码实现

代码参考：

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        int low = 0;
        int high = nums.Length - 1;
        int mid = 0;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (target == nums[mid]) return mid;
            else if (target > nums[mid]) low = mid + 1;
            else high = mid - 1;
        }
        if (target > nums[mid]) return mid + 1;
        else return mid;
    }
}

image.png

3、时间复杂度

时间复杂度 ： O(log n)

其中n为nums数组的大小，时间复杂度为二分查找的时间复杂度O(log n)

空间复杂度： O(1)

只需要常数级别的空间存放变量。

三、总结

二分查找的思路不难理解，但是边界条件容易出错。

比如 循环结束条件中 left 和 right 的关系，更新 left 和 right 位置时要不要加 1 减 1。

设置数组长度可以忽略边界条件的判断，因为存在一种情况是target大于数组中的所有数，此时需要插入到数组长度的位置。