35. 搜索插入位置

题目

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

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

难度：🌟🌟

示例 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

提示:

• 1 <= nums.length <= 10⁴
• -10⁴ <= nums[i] <= 10⁴
• nums 为 无重复元素 的 升序 排列数组
• -10⁴ <= target <= 10⁴

题解

本题本质是使用二分搜索查找左边界问题。注意事项有：

1. 查找左边界不存在死循环问题
2. 防止 left 下标越界，需要做边界校验

代码实现

// 这题本质是在 nums 中查找匹配 target 的左边界
func searchInsert(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := left + (right-left)/2
		if nums[mid] > target {
			// 搜索区间变为 [left, mid-1]
			right = mid - 1
		} else if nums[mid] < target {
			// 搜索区间变为 [mid+1, right]
			left = mid + 1
		} else if nums[mid] == target {
			right = mid
		}
	}
	if left < len(nums) && nums[left] >= target {
		return left
	}
	return left + 1
}