024-搜索插入位置 (Search Insert Position)

LeetCode 第24题 - 搜索插入位置的详细题解，包含二分查找算法和JavaScript实现

题目描述

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

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

示例 4：

输入: nums = [1,3,5,6], target = 0
输出: 0

示例 5：

输入: nums = [1], target = 0
输出: 0

解题思路

二分查找法（推荐）

由于数组是有序的，我们可以使用二分查找来找到目标值的插入位置。

核心思想：

使用二分查找找到目标值的位置
如果找到目标值，直接返回其索引
如果没有找到目标值，返回应该插入的位置
插入位置就是第一个大于目标值的位置

算法步骤：

使用二分查找，维护左右边界
如果中间元素等于目标值，返回中间位置
如果中间元素小于目标值，在右半部分查找
如果中间元素大于目标值，在左半部分查找
最终返回左边界，这就是插入位置

JavaScript 解决方案

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    // 如果没有找到目标值，返回插入位置
    return left;
};

复杂度分析

时间复杂度：O(log n)

使用二分查找，每次将查找范围缩小一半
总共进行 O(log n) 次比较

空间复杂度：O(1)

只使用了常数额外空间

测试用例

// 测试函数
function testSearchInsert() {
    const testCases = [
        { nums: [1,3,5,6], target: 5, expected: 2 },
        { nums: [1,3,5,6], target: 2, expected: 1 },
        { nums: [1,3,5,6], target: 7, expected: 4 },
        { nums: [1,3,5,6], target: 0, expected: 0 },
        { nums: [1], target: 0, expected: 0 },
        { nums: [1], target: 1, expected: 0 },
        { nums: [1], target: 2, expected: 1 },
        { nums: [1,3,5], target: 4, expected: 2 },
        { nums: [1,3,5], target: 6, expected: 3 },
        { nums: [1,3,5], target: 0, expected: 0 },
        { nums: [1,3,5,7,9], target: 4, expected: 2 },
        { nums: [1,3,5,7,9], target: 8, expected: 4 },
        { nums: [1,3,5,7,9], target: 10, expected: 5 },
        { nums: [1,3,5,7,9], target: 0, expected: 0 }
    ];
    
    testCases.forEach((testCase, index) => {
        const result = searchInsert(testCase.nums, testCase.target);
        const passed = result === testCase.expected;
        console.log(`测试用例 ${index + 1}: ${passed ? '✅' : '❌'}`);
        console.log(`输入: nums = [${testCase.nums}], target = ${testCase.target}`);
        console.log(`期望: ${testCase.expected}`);
        console.log(`实际: ${result}`);
        console.log('---');
    });
}

// 运行测试
testSearchInsert();

关键点总结

二分查找：利用数组的有序性进行高效的二分查找
插入位置：如果没有找到目标值，左边界就是插入位置
边界处理：注意数组为空和目标值在边界的情况
相等处理：如果找到目标值，直接返回其位置
循环结束：当左边界大于右边界时，左边界就是插入位置

总结

这道题是二分查找的经典应用，考察了对二分查找算法的理解和边界处理能力。

考察重点：

二分查找算法的应用
边界条件的处理
数组有序性的利用
代码的简洁性和可读性
算法的时间复杂度分析

这道题是很多面试中的常见题目，掌握二分查找的技巧对于解决类似问题很有帮助。在实际面试中，建议先分析问题，然后设计二分查找算法。

024-搜索插入位置 (Search Insert Position)

On this page