让我们一起啃算法----搜索插入位置
摘要: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 }。如果 二分查找 结束仍是没有找到 target 的值 ,最后返回 left 就可以了,至于为什么 left 的值是 target 插入的位置,可以看流程图的分析。
搜索插入位置( 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 }
总结
欢迎关注我们的微信公众号,每天学习Go知识