题目描述#

给定一个已经按升序排列的数组 nums 和一个目标值 target，需要在数组中找到 target 的下标。

如果 target 不存在，就返回它按顺序插入时应该在的位置。题目要求时间复杂度必须是 O(log n)，所以不能从头扫到尾啦，拜托，二分查找该出场了嘛～

嘿嘿，排序数组已经排好队啦，咱只要拿相机对准中间位置咔嚓一下～

思路#

这题的关键不是单纯判断 target 在不在，而是要找到 第一个大于等于 target 的位置。如果这个位置上的值正好等于 target，那它就是目标下标；如果循环结束都没找到，left 停下来的位置就是插入点。

咱用闭区间 [left, right] 来维护还可能存在答案的范围。每次取中点 mid，如果 nums[mid] == target，直接返回；如果 nums[mid] > target，说明目标值或者插入位置一定在左边，于是让 right = mid - 1；否则说明 nums[mid] < target，插入点肯定在右边，于是让 left = mid + 1。

循环条件是 left <= right，当循环结束时，区间已经空了，并且一定满足 right + 1 == left。这个时候 left 就是第一个满足 nums[i] >= target 的下标，也就是答案。没错没错，二分最迷人的地方就是：每次砍掉一半，最后还能精确停在该停的位置。

照片当然不是现实，但如果每次都把边界拍清楚，是不是就能更接近正确答案一些呢？好啦说多了——来，笑一个，三、二、一，咔嚓！

思维边界#

• 闭区间写法：left 和 right 都是当前仍可能存在答案的位置，因此循环条件使用 left <= right。
• 中点计算：mid := left + (right-left)/2 可以避免 left + right 潜在溢出，是二分查找的好习惯。
• 插入位置：目标值不存在时，循环结束后的 left 就是第一个大于等于 target 的位置。
• 右侧插入：如果 target 比所有元素都大，最后 left == len(nums)，表示插入到数组末尾。
• 左侧插入：如果 target 比所有元素都小，right 会一路左移，最后返回 0。

本姑娘宣布：记住“返回 left”，这题就稳稳拿下啦～

代码#

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 {
			return mid
		} else if nums[mid] > target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	// left是第一个满足条件的下标
	return left
}