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

请必须使用时间复杂度为 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

题目解析

核心题意：

• 给定一个严格升序（无重复元素）的数组 nums 和一个目标值 target。
• 如果在数组中能找到 target，返回其所在的下标。
• 如果找不到，返回它按照升序规律应该被插入的位置下标。
• 强制要求：算法的时间复杂度必须为 $O(\log n)$。

考察重点： 当你看到“已排序的数组”并且要求时间复杂度达到 $O(\log n)$ 时，这可以说是最明显的 二分查找（Binary Search） 信号。本题的难点不仅在于找到目标值，更在于在找不到目标值时，如何准确判断并返回其插入位置。

解题思路

采用经典的二分查找算法即可完美解决此题。

思路推导：

1. 设定两个指针 left 和 right，分别指向数组的起始位置 0 和结束位置 nums.length - 1。
2. 在 left <= right 的前提下，进行循环：
   • 计算中间位置 mid。为了防止数值溢出，我们通常使用 mid = left + (right - left) / 2。
   • 情况 A：如果 nums[mid] == target，说明找到了目标值，直接返回 mid 即可。
   • 情况 B：如果 nums[mid] < target，说明 target 如果存在，必然在 mid 的右侧。因此我们将左边界更新为 left = mid + 1。
   • 情况 C：如果 nums[mid] > target，说明 target 如果存在，必然在 mid 的左侧。因此我们将右边界更新为 right = mid - 1。
3. 关键点（当目标值不存在时如何返回插入位置）：
   • 当循环正常结束（即 left > right 时），说明数组中不存在 target。
   • 此时，left 所指向的位置正是 target 应该插入的位置。
   • 为什么呢？因为在二分查找结束前的最后一步，left 和 right 是相等的（即 left == right == mid）。
     • 如果此时 nums[mid] < target，target 应该插入在 mid 的后一位，接下来 left 会更新为 mid + 1，恰好对应插入位置。
     • 如果此时 nums[mid] > target，target 就应该插入在当前的 mid 位置，接下来 right 会更新为 mid - 1，而 left 依然停留在 mid，刚好也就是我们要找的插入位置。
   • 所以，无论哪种情况，当循环结束时，直接返回 left 即可。

复杂度分析

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

Java 实现

class Solution {
    public int searchInsert(int[] nums, int target) {
        // 定义左右边界指针
        int left = 0;
        int right = nums.length - 1;
        
        // 当左边界小于等于右边界时，可以继续查找
        while (left <= right) {
            // 计算中间位置，防止 (left + right) 直接相加导致整型溢出
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                // 如果刚好找到了目标值，直接返回对应的索引
                return mid;
            } else if (nums[mid] < target) {
                // 如果中间值小于目标值，说明目标值可能在右半部分
                // 缩小查找范围至 [mid + 1, right]
                left = mid + 1;
            } else {
                // 如果中间值大于目标值，说明目标值可能在左半部分
                // 缩小查找范围至 [left, mid - 1]
                right = mid - 1;
            }
        }
        
        // 当循环结束且未找到目标值时，left 和 right 会发生交错 (left = right + 1)
        // 此时 left 指向的位置正是第一个大于 target 的元素位置，
        // 也就是 target 按照顺序应该被插入的位置。
        return left;
    }
}