题目：search-insert-position

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

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

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

解题思路

这道题是标准的二分查找插入点，重点在于如果找不到目标值，那么 left 就是要插入的点。

Java 实现

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        // 当循环结束且未找到目标值时，left 和 right 会发生交错 (left = right + 1)
        // 此时 left 就是要插入的点
        return left;
    }
}

复杂度分析

• 时间复杂度：$O(\log n)$，其中 $n$ 是数组的长度。每次查找都会将搜索区间缩小一半，符合二分查找的时间复杂度要求。
• 空间复杂度：$O(1)$，只使用了 left、right 和 mid 等几个常数级别的辅助变量。

扩展

如果题目说包含重复元素：

• 要找最左点， 只需要继续二分，不要命中就return ，二分到最后 i 就是要插入的点
• 要找最右点，可以取巧为找比原来要找的数大0.5的数，再左一格

参考：《Hello 算法》二分查找插入点