35.实现一个算法在一个有序数组中查找目标值，如果没找到则返回目标值应该被插入的位置

本文主要是介绍35.实现一个算法在一个有序数组中查找目标值，如果没找到则返回目标值应该被插入的位置，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

35. Search Insert Position

题目

给定一个排序数组和一个目标值，如果找到目标值，则返回其索引。如果没有找到，则返回按顺序插入时它应该在的位置的索引。

你可以假设数组中没有重复的元素。

示例 1：

输入: [1,3,5,6], 5
输出: 2

示例 2：

输入: [1,3,5,6], 2
输出: 1

示例 3：

输入: [1,3,5,6], 7
输出: 4

示例 4：

输入: [1,3,5,6], 0
输出: 0

解题思路

给出一个已经从小到大排序后的数组，要求在数组中找到插入 target 元素的位置。
这一题是经典的二分搜索的变种题，在有序数组中找到最后一个比 target 小的元素。

代码实现

// 实现步骤
//初始化两个指针 low 和 high 分别指向数组的起始和结束位置。
//使用二分查找法不断缩小搜索范围。
//根据中间元素 nums[mid] 的值与目标值 target 的比较，调整搜索范围。
//最终在找到目标值应插入的位置时返回结果。
package leetcodefunc searchInsert(nums []int, target int) int {low, high := 0, len(nums)-1  // 初始化搜索的左右边界，low 为左边界，high 为右边界for low <= high {  // 当左边界小于或等于右边界时，继续搜索mid := low + (high-low)>>1  // 计算中间位置，防止溢出if nums[mid] >= target {  // 如果中间元素大于或等于目标值high = mid - 1  // 调整右边界，缩小搜索范围} else {  // 如果中间元素小于目标值if (mid == len(nums)-1) || (nums[mid+1] >= target) {  // 检查是否到达数组末尾或下一个元素大于等于目标值return mid + 1  // 返回应插入的位置}low = mid + 1  // 调整左边界，继续向右搜索}}return 0  // 如果目标值小于数组中的所有元素，返回 0 作为插入位置
}

复杂度分析

时间复杂度: O(log n)，因为使用了二分查找。
空间复杂度: O(1)，只使用了常数级别的额外空间。

测试代码

package leetcodeimport ("fmt""testing"
)type question35 struct {para35ans35
}// para 是参数
// one 代表第一个参数
type para35 struct {nums   []inttarget int
}// ans 是答案
// one 代表第一个答案
type ans35 struct {one int
}func Test_Problem35(t *testing.T) {qs := []question35{{para35{[]int{1, 3, 5, 6}, 5},ans35{2},},{para35{[]int{1, 3, 5, 6}, 2},ans35{1},},{para35{[]int{1, 3, 5, 6}, 7},ans35{4},},{para35{[]int{1, 3, 5, 6}, 0},ans35{0},},}fmt.Printf("------------------------Leetcode Problem 35------------------------\n")for _, q := range qs {_, p := q.ans35, q.para35fmt.Printf("【input】:%v       【output】:%v\n", p, searchInsert(p.nums, p.target))}fmt.Printf("\n\n\n")
}