欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net

摘要

搜索插入位置工具实现了在有序数组中查找目标值的插入位置，如果目标值已存在则返回其索引的功能。本文详细解析了输入解析、二分查找法、线性查找法、插入位置计算等核心功能的代码实现细节。

1. 算法背景

1.1 问题描述

给定一个有序数组和一个目标值，找出目标值的插入位置。如果目标值已存在于数组中，返回其索引；如果不存在，返回应该插入的位置索引。

示例：

• 数组：[1, 3, 5, 6]
• 目标值：5
• 结果：2（目标值已存在）

1.2 应用场景

• 查找操作
• 插入操作
• 维护有序数据结构
• 算法竞赛

2. 核心算法原理

2.1 二分查找法

利用数组有序的特性，使用二分查找快速定位插入位置。时间复杂度 O(log n)，空间复杂度 O(1)。

2.2 线性查找法

从数组开头遍历，找到第一个大于等于目标值的位置。时间复杂度 O(n)，空间复杂度 O(1)。

3. 代码实现详细解析

3.1 输入解析模块

var nums: List<Int>? = null
var targetValue = 0

payload.lines()
    .map { it.trim() }
    .filter { it.isNotEmpty() }
    .forEach { line ->
        when {
            line.startsWith("nums=", ignoreCase = true) -> {
                val valuesStr = line.substringAfter("=").trim()
                try {
                    nums = valuesStr.split(",")
                        .map { it.trim() }
                        .filter { it.isNotEmpty() }
                        .map { it.toInt() }
                        .sorted()
                } catch (e: Exception) {
                    nums = null
                }
            }
            line.startsWith("target=", ignoreCase = true) -> {
                try {
                    targetValue = line.substringAfter("=").trim().toInt()
                } catch (e: Exception) {
                    targetValue = 0
                }
            }
        }
    }

代码解析：

这段代码实现了灵活的输入解析机制，支持从输入字符串中提取数组和目标值。首先声明两个变量：nums 是一个可空整数列表，用于存储解析后的数组；targetValue 是目标值，初始值为 0。

然后使用函数式编程风格处理输入：payload.lines() 将输入按行分割，map { it.trim() } 去除每行的首尾空白字符，filter { it.isNotEmpty() } 过滤空行。

在 forEach 循环中，使用 when 表达式进行模式匹配。第一个分支处理 nums= 格式的输入：提取等号后面的部分作为数组字符串，然后使用 split(",") 按逗号分割，map { it.trim() } 去除空白字符，filter { it.isNotEmpty() } 过滤空元素，map { it.toInt() } 转换为整数。

注意这里使用 sorted() 对数组进行排序，确保数组是有序的。这是算法的前提条件，因为二分查找只能在有序数组上进行。

使用 try-catch 块捕获可能的异常，确保程序的健壮性。

第二个分支处理 target= 格式的输入：提取等号后面的部分并转换为整数。如果解析失败，保持目标值为 0。

如果解析后数组为 null，则尝试直接解析输入：将第一行按逗号分割并转换为整数数组，并进行排序。第二行作为目标值。这种备选方案提高了输入格式的灵活性。

3.2 二分查找法实现

fun searchInsertBinarySearch(nums: List<Int>, target: Int): Int {
    var left = 0
    var right = nums.size - 1

    while (left <= right) {
        val mid = left + (right - left) / 2

        when {
            nums[mid] == target -> return mid
            nums[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }

    return left
}

代码解析：

这是二分查找法的核心实现，利用数组有序的特性快速定位插入位置。函数接受一个有序数组和目标值作为参数，返回插入位置的索引。

首先初始化两个指针：left 指向数组的开头（索引 0），right 指向数组的末尾（索引 nums.size - 1）。这两个指针定义了当前搜索的范围。

然后使用 while 循环，条件是 left <= right，即左指针还没有超过右指针。在循环内部，首先计算中间位置的索引：val mid = left + (right - left) / 2。

这里使用 left + (right - left) / 2 而不是 (left + right) / 2 是为了避免整数溢出。虽然对于大多数情况来说不会溢出，但这是良好的编程实践，特别是在处理大数组时。

然后使用 when 表达式根据中间元素与目标值的关系进行处理：

如果 nums[mid] == target，说明找到了目标值，直接返回中间索引 mid。这是最简单的情况，目标值已经存在于数组中。

如果 nums[mid] < target，说明中间元素小于目标值，目标值应该在右半部分。将左指针移动到中间位置的右边：left = mid + 1。这样搜索范围缩小到右半部分。

否则（nums[mid] > target），说明中间元素大于目标值，目标值应该在左半部分。将右指针移动到中间位置的左边：right = mid - 1。这样搜索范围缩小到左半部分。

循环会一直执行，直到找到目标值（提前返回）或者左指针超过右指针（left > right）。当循环结束时，如果还没有找到目标值，说明目标值不存在于数组中。

此时，left 指针就是目标值应该插入的位置。这是因为：

• 如果目标值小于所有元素，left 会一直保持在 0（数组开头）
• 如果目标值大于所有元素，left 会一直增加到 nums.size（数组末尾）
• 如果目标值在数组范围内，left 会指向第一个大于目标值的位置，这正是应该插入的位置

最后返回 left，这就是目标值的插入位置。这个算法的时间复杂度是 O(log n)，其中 n 是数组的长度，因为每次循环都将搜索范围减半。空间复杂度是 O(1)，因为只使用了固定数量的变量。

3.3 线性查找法实现

fun searchInsertLinear(nums: List<Int>, target: Int): Int {
    for (i in nums.indices) {
        if (nums[i] >= target) {
            return i
        }
    }
    return nums.size
}

代码解析：

这是线性查找法的实现，通过遍历数组找到插入位置。函数接受一个有序数组和目标值作为参数，返回插入位置的索引。

使用 for 循环遍历数组的所有元素，循环变量 i 是当前元素的索引。在循环内部，检查当前元素是否大于等于目标值（nums[i] >= target）。

如果当前元素大于等于目标值，说明找到了插入位置。因为数组是有序的，第一个大于等于目标值的位置就是目标值应该插入的位置。如果目标值已存在，这个位置就是目标值的索引；如果目标值不存在，这个位置就是应该插入的位置。

直接返回当前索引 i，这是插入位置。

如果循环结束还没有返回，说明目标值大于数组中的所有元素，应该插入到数组的末尾。返回数组的长度 nums.size，这就是末尾位置的索引（在插入时，新元素会插入到这个位置，即数组的末尾）。

这个算法的时间复杂度是 O(n)，其中 n 是数组的长度，因为最坏情况下需要遍历整个数组。空间复杂度是 O(1)，因为只使用了固定数量的变量。

虽然时间复杂度较高，但线性查找法的实现非常简单直观，容易理解。对于较小的数组，这种方法的性能差异并不明显，而且代码更加简洁。

3.4 二分查找过程分析

while (left <= right) {
    val mid = left + (right - left) / 2
    val midValue = numArray[mid]

    builder.appendLine("步骤 $step:")
    builder.appendLine("  left = $left, right = $right")
    builder.appendLine("  mid = $left + ($right - $left) / 2 = $mid")
    builder.appendLine("  nums[$mid] = $midValue")

    when {
        midValue == targetValue -> {
            builder.appendLine("  ✅ 找到目标值！返回索引 $mid")
            break
        }
        midValue < targetValue -> {
            builder.appendLine("  $midValue < $targetValue，目标值在右半部分")
            builder.appendLine("  left = $mid + 1 = ${mid + 1}")
            left = mid + 1
        }
        else -> {
            builder.appendLine("  $midValue > $targetValue，目标值在左半部分")
            builder.appendLine("  right = $mid - 1 = ${mid - 1}")
            right = mid - 1
        }
    }
}

代码解析：

这段代码实现了详细的二分查找过程分析，帮助用户理解算法是如何逐步缩小搜索范围的。首先使用 while 循环，条件是 left <= right。

在每一步中，计算中间位置并输出详细信息，包括左右指针的位置、中间位置的计算过程和中间元素的值。然后根据中间元素与目标值的关系进行处理。

如果找到目标值，输出成功信息并跳出循环。如果中间元素小于目标值，说明目标值在右半部分，输出移动左指针的信息并更新左指针。如果中间元素大于目标值，说明目标值在左半部分，输出移动右指针的信息并更新右指针。

这种详细的输出对于教学和调试非常有用，用户可以清楚地看到算法是如何通过逐步缩小搜索范围来定位插入位置的。

4. 算法复杂度分析

4.1 时间复杂度

• 二分查找法：O(log n)，每次循环将搜索范围减半
• 线性查找法：O(n)，最坏情况下需要遍历整个数组
• 总体时间复杂度：O(log n)（使用二分查找法）

4.2 空间复杂度

• 二分查找法：O(1)，只使用固定数量的变量
• 线性查找法：O(1)，只使用固定数量的变量
• 总体空间复杂度：O(1)

5. 算法优化建议

5.1 二分查找法优化

二分查找法已经是时间最优的算法，时间复杂度为 O(log n)。

5.2 边界条件处理

代码已经处理了各种边界情况：目标值小于所有元素、大于所有元素、已存在等情况。

5.3 数组排序

算法假设数组是有序的，如果输入数组无序，需要在解析时进行排序。

6. 应用场景扩展

1. 查找操作：在有序数组中查找元素的插入位置
2. 插入操作：维护有序数据结构的插入操作
3. 范围查找：查找满足条件的元素范围
4. 算法竞赛：LeetCode 等平台的经典问题
5. 扩展问题：查找边界、查找范围等变体

7. 总结

搜索插入位置工具实现了两种查找方法，核心要点：

1. 二分查找法：时间复杂度 O(log n)，利用数组有序特性快速定位
2. 线性查找法：时间复杂度 O(n)，实现简单但效率较低
3. 插入位置计算：当目标值不存在时，left 指针就是插入位置
4. 边界处理：正确处理目标值小于、大于、等于数组元素的各种情况

通过深入理解代码实现，可以更好地应用这个算法解决实际问题，如查找操作、插入操作、维护有序数据结构等场景。二分查找法的思想也可以扩展到其他类似的搜索问题中。