一、题目
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; } } 复制代码
网络异常,图片无法展示
|
3、时间复杂度
时间复杂度 : O(log n)
其中n为nums数组的大小,时间复杂度为二分查找的时间复杂度O(log n)
空间复杂度: O(1)
只需要常数级别的空间存放变量。
三、总结
二分查找的思路不难理解,但是边界条件容易出错。
比如 循环结束条件中 left 和 right 的关系,更新 left 和 right 位置时要不要加 1 减 1。
设置数组长度可以忽略边界条件的判断,因为存在一种情况是target大于数组中的所有数,此时需要插入到数组长度的位置。