写点什么

【刷题第六天】35. 搜索插入位置

作者:白日梦
  • 2022 年 5 月 12 日
  • 本文字数:789 字

    阅读完需:约 3 分钟

一、题目描述:

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

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

示例 1:

输入: nums = [1,3,5,6], target = 5

输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2

输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7

输出: 4

二、思路分析:

题目与以往接触略有区别,以往题目大多只有搜索索引情况,但本题目加入了如果搜索不到,则添加到对应位置。

虽然增加了一个额外条件,但第一想法还是二分查找,只不过在于如何修改条件,能满足额外情况。

二分查找变体一般都在与修改判断条件。我们考虑插入位置 pos,应该满足下列条件:

nums[pos−1]< target <=nums[pos]

nums[pos-1]< target <=nums[pos]

nums[pos−1]< target <=nums[pos]

nums 为排列数组,如果存在这个值,最终的结果也是返回 pos 位置,如果不存在则在 pos 位置插入值,因此本题目可以转化为 寻找第一个大于等于 target 的下标

通过上面的分析,我们已经成功的把该问题转化为了二分查找问题,下面开始套模板: 即通过使用二分法逼近查找第一个大于等于 target 的下标。

如果 target 大于数组中的所有元素,就会插入在第 n 个位置。因此下面代码中 res 初始值赋值为 n,可以避免这种情况的特殊判断。

三、AC 代码:

var searchInsert = function (nums, target) {  const n = nums.length;  let start = 0;  let end = n - 1;  // 处理临界情况  let res = n;
while (start <= end) { // 避免越界 let mid = (end - start) / 1 + start; if (target <= nums[mid]) { res = mid; end = mid - 1; } else { start = mid + 1; } } return res;};复制代码
复制代码

四、总结:

好久没有做二分查找的问题了,第一瞬间竟然没有转化好,转化成功后,可以很清楚的看到这就是个二分问题。加油!!!


用户头像

白日梦

关注

还未添加个人签名 2022.03.10 加入

还未添加个人简介

评论

发布
暂无评论
【刷题第六天】35. 搜索插入位置_5月月更_白日梦_InfoQ写作社区