搜索插入位置（ Search-Insert-Position ）

题干：

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
  输入: [1,3,5,6], 5
  输入: 输出: 2
示例 3:
  输入: 输入: [1,3,5,6], 7
  输入: 输出: 4
示例 4:
  输入: 输入: [1,3,5,6], 0
  输入: 输出: 0
来源：力扣

这题主要应用 二分查找 的思路来解题，题目是比较简单的，但是 二分查找 这个思路还是蛮重要的。

解题思路

一般使用 二分查找 都需要先对原数组进行排序，题中给到的数组是已经排序的，因此这一步可以省去。

二分查找 思路比较简单，首先初始化三个指针： left 指向 nums 最左边的元素，right 指向 nums 右边的元素，根据 left 和 right 计算 mid 指针。我们先拿目标值 target 与 nums[mid] 进行比较。

如果 target > nums[mid]，说明要查找的值有可能在 nums[mid+1, right] 之间，这时候将 left 赋值为 mid + 1，right 不变，重新计算一下 mid，重新比较。

如果 target < nums[mid]，说明要查找的值有可能在 nums[left, mid-1] 之间，这时候将 right 赋值为 mid – 1，left 不变，重新计算一下mid，重新比较。

如果 target == nums[mid]，那么恭喜找到啦，根据题意，找到的索引值就是 target 插入的目标位置，即返回 mid 即可。

如果 二分查找 结束仍是没有找到 target 的值，最后返回 left 就可以了，至于为什么 left 的值是 target 插入的位置，可以看流程图的分析。

mid 的计算方式： mid = left + ( rigth – left ) / 2，至于为什么不用 ( left + right ) / 2 来计算 mid 是因为 right + left 有可能溢出。
注： ( right – left) / 2 取整，因为数组的索引值是整数。

流程图如下：

代码实现

// 函数的实现并不是最简洁的，但是整个二分法思路是很清晰的。func searchInsert(nums []int, target int) int {    if len(nums) <= 0 {        return 0    }    var left, right = 0, len(nums) - 1    for left <= right {        // 根据 left 和 right 计算 mid 的值        mid := left + (right - left) / 2  // ( left + right ) / 2        // 目标值大于中间值，left = mid + 1        if nums[mid] < target {            left = mid + 1        // 目标值小于中间值 right = mid - 1        } else if nums[mid] > target {            right = mid - 1        } else {            // 目标值等于中间值返回 mid，即为目标值需要插入的位置            return mid        }    }    // 找不到目标值，这时候返回left就是目标值需要插入的位置    return left}

总结

每天进步一点点，加油！
算法教程项目，每天更新一题，点个 star 支持一下呀：
https://github.com/wx-satellite/learning-a…

标签: 二分 数组 输入

给这篇文章的作者打赏

微信扫一扫打赏

支付宝扫一扫打赏

×

打赏 点赞(1)