1 题目描述

35. 搜索插入位置要求根据给定一个排序数组 nums 和一个目标值 target，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，则返回它将会被按顺序插入的位置。要求使用的时间复杂度为 O(log n)。

2 解题思路

由于题目要求使用 O(log n) 的时间复杂度，我们自然想到使用二分查找法来解决这个问题。二分查找的基本思想是在有序数组中查找一个值，每次比较中间元素，根据比较结果缩小查找范围直到找到目标或者确定目标不在数组中。

对于本题，我们需要做以下调整以处理目标值不存在的情况：

1. 初始化：定义两个指针 left 和 right 分别表示搜索区间的起始和结束位置。
2. 循环条件：当 left <= right 时，搜索区间有效，继续执行循环。
3. 中间位置：计算中间位置 middle = left + (right - left) / 2，这样可以避免整数溢出。
4. 比较并更新：
   • 如果 nums[middle] == target，则找到目标值，返回 middle。
   • 如果 nums[middle] > target，则目标值在左侧子数组中，更新 right = middle - 1。
   • 如果 nums[middle] < target，则目标值在右侧子数组中，更新 left = middle + 1。
5. 终止条件：如果退出循环，说明没有找到目标值。此时 left 指针指向了应该插入的位置，返回 left。

3 Java 代码实现

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int middle = left + (right - left) / 2;
            
            if (nums[middle] == target) {
                return middle; // 直接返回匹配的索引
            } else if (nums[middle] < target) {
                left = middle + 1; // 缩小左侧范围
            } else {
                right = middle - 1; // 缩小右侧范围
            }
        }
        
        return left; // 循环结束后，left 指向目标应该插入的位置
    }
}

3.1.1.1 注意事项

• 确保在计算中间位置时使用 left + (right - left) / 2 而不是 (left + right) / 2 来避免整数溢出问题。
• 初始设置 right 为 nums.length - 1，这是因为索引从 0 开始，最后一个元素的索引是 length - 1。
• 循环条件是 left <= right 而不是 left < right，这是因为我们需要包含 left == right 的情况，这可能是目标值所在的单个元素。
• 退出循环终止时，left 指向了数组中第一个大于或等于 target 的元素的位置，或者是数组末尾的下一个位置（如果所有元素都小于 target），因此直接返回left即可。