35.搜索插入位置

LeetCode LeetCode 热题100 数组 二分查找
发布时间 :
字数:2.4k 阅读 : 评论:
  1. 35.搜索插入位置
    1. 35.1 题目
    2. 35.2 题解
      1. 方法一：迭代版二分查找（推荐）
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：递归版二分查找
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 35.3 代码
    4. 35.4 运行结果

35.搜索插入位置

35.1 题目

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

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

提示：

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 为无重复元素的升序排列数组
  • -10^4 <= target <= 10^4

35.2 题解

方法一：迭代版二分查找（推荐）

思路

二分查找的本质：不断缩小搜索范围，在 O(log n) 时间内找到目标或确定插入位置。

每次计算中间位置 mid，比较 nums[mid] 与 target：

  • 相等：找到目标，返回 mid
  • nums[mid] < target：目标在右半部分，left = mid + 1
  • nums[mid] > target：目标在左半部分，right = mid - 1

循环结束时，left 就是插入位置。为什么？因为 left 是第一个大于 target 的位置索引。

举个例子：nums = [1,3,5,6], target = 2

  • left=0, right=3, mid=1, nums[1]=3 > 2 → right=0
  • left=0, right=0, mid=0, nums[0]=1 < 2 → left=1
  • left > right，循环结束，返回 left=1
  • 插入位置是1，正确！

复杂度分析

  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)

代码

// 方法一：迭代版二分查找（推荐，时间复杂度 O(log n)）
// 核心思想：通过不断缩小搜索范围，找到目标值或确定插入位置
// 1. 初始化左右指针 left=0, right=nums.Length-1
// 2. 当 left <= right 时，计算中间位置 mid
// 3. 比较 nums[mid] 与 target：
//    - 相等：直接返回 mid（找到目标值）
//    - nums[mid] < target：目标值在右半部分，left = mid + 1
//    - nums[mid] > target：目标值在左半部分，right = mid - 1
// 4. 循环结束时，left 即为插入位置（因为此时 left > right，且 left 是第一个大于 target 的位置）
static int SearchInsertBinarySearch(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)
        {
            // 目标值在右半部分，缩小左边界
            left = mid + 1;
        }
        else
        {
            // 目标值在左半部分，缩小右边界
            right = mid - 1;
        }
    }

    // 循环结束，left 即为插入位置
    return left;
}

方法二：递归版二分查找

思路

与迭代版逻辑一致，但使用递归实现。

递归终止条件：left > right，此时返回 left 作为插入位置。

每次递归根据比较结果缩小搜索范围：[left, mid-1] 或 [mid+1, right]。

递归版代码更简洁，但实际应用中迭代版更常用（避免递归栈开销）。

复杂度分析

  • 时间复杂度：O(log n)
  • 空间复杂度：O(log n)，递归栈

代码

// 方法二：递归版二分查找（补充，时间复杂度 O(log n)）
// 核心思想：通过递归不断缩小搜索范围，逻辑与迭代版一致
static int SearchInsertRecursive(int[] nums, int target)
{
    return SearchInsertRecursiveHelper(nums, target, 0, nums.Length - 1);
}

// 递归辅助函数
// nums：原始数组
// target：目标值
// left：当前搜索范围的左边界
// right：当前搜索范围的右边界
static int SearchInsertRecursiveHelper(int[] nums, int target, int left, int right)
{
    // 终止条件：搜索范围为空，返回 left 作为插入位置
    if (left > right)
    {
        return left;
    }

    // 计算中间位置
    int mid = left + (right - left) / 2;

    if (nums[mid] == target)
    {
        // 找到目标值，直接返回索引
        return mid;
    }
    else if (nums[mid] < target)
    {
        // 目标值在右半部分，递归搜索 [mid+1, right]
        return SearchInsertRecursiveHelper(nums, target, mid + 1, right);
    }
    else
    {
        // 目标值在左半部分，递归搜索 [left, mid-1]
        return SearchInsertRecursiveHelper(nums, target, left, mid - 1);
    }
}

35.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
        // 请必须使用时间复杂度为 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
        //
        // 提示：
        // 1 <= nums.length <= 10^4
        // -10^4 <= nums[i] <= 10^4
        // nums 为无重复元素的升序排列数组
        // -10^4 <= target <= 10^4

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { 1, 3, 5, 6 };
        int target1 = 5;
        int result1 = SearchInsertBinarySearch(nums1, target1);
        Console.WriteLine($"示例1 二分查找 方法 输入：{FormatArray(nums1)}, target={target1} 输出：{result1}");
        int result1_2 = SearchInsertRecursive(nums1, target1);
        Console.WriteLine($"示例1 递归二分 方法 输入：{FormatArray(nums1)}, target={target1} 输出：{result1_2}");

        // 示例 2
        int[] nums2 = { 1, 3, 5, 6 };
        int target2 = 2;
        int result2 = SearchInsertBinarySearch(nums2, target2);
        Console.WriteLine($"示例2 二分查找 方法 输入：{FormatArray(nums2)}, target={target2} 输出：{result2}");
        int result2_2 = SearchInsertRecursive(nums2, target2);
        Console.WriteLine($"示例2 递归二分 方法 输入：{FormatArray(nums2)}, target={target2} 输出：{result2_2}");

        // 示例 3
        int[] nums3 = { 1, 3, 5, 6 };
        int target3 = 7;
        int result3 = SearchInsertBinarySearch(nums3, target3);
        Console.WriteLine($"示例3 二分查找 方法 输入：{FormatArray(nums3)}, target={target3} 输出：{result3}");
        int result3_2 = SearchInsertRecursive(nums3, target3);
        Console.WriteLine($"示例3 递归二分 方法 输入：{FormatArray(nums3)}, target={target3} 输出：{result3_2}");

        // 示例 4
        int[] nums4 = { 1, 3, 5, 6 };
        int target4 = 0;
        int result4 = SearchInsertBinarySearch(nums4, target4);
        Console.WriteLine($"示例4 二分查找 方法 输入：{FormatArray(nums4)}, target={target4} 输出：{result4}");
        int result4_2 = SearchInsertRecursive(nums4, target4);
        Console.WriteLine($"示例4 递归二分 方法 输入：{FormatArray(nums4)}, target={target4} 输出：{result4_2}");

        // 示例 5
        int[] nums5 = { 1 };
        int target5 = 0;
        int result5 = SearchInsertBinarySearch(nums5, target5);
        Console.WriteLine($"示例5 二分查找 方法 输入：{FormatArray(nums5)}, target={target5} 输出：{result5}");
        int result5_2 = SearchInsertRecursive(nums5, target5);
        Console.WriteLine($"示例5 递归二分 方法 输入：{FormatArray(nums5)}, target={target5} 输出：{result5_2}");

        #endregion
    }

    #region 辅助方法

    // 辅助方法：格式化数组为字符串，方便输出
    static string FormatArray(int[] nums)
    {
        if (nums == null || nums.Length == 0) return "[]";
        return $"[{string.Join(",", nums)}]";
    }

    #endregion

    #region 答案

    // 方法一：迭代版二分查找（推荐，时间复杂度 O(log n)）
    // 核心思想：通过不断缩小搜索范围，找到目标值或确定插入位置
    // 1. 初始化左右指针 left=0, right=nums.Length-1
    // 2. 当 left <= right 时，计算中间位置 mid
    // 3. 比较 nums[mid] 与 target：
    //    - 相等：直接返回 mid（找到目标值）
    //    - nums[mid] < target：目标值在右半部分，left = mid + 1
    //    - nums[mid] > target：目标值在左半部分，right = mid - 1
    // 4. 循环结束时，left 即为插入位置（因为此时 left > right，且 left 是第一个大于 target 的位置）
    static int SearchInsertBinarySearch(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)
            {
                // 目标值在右半部分，缩小左边界
                left = mid + 1;
            }
            else
            {
                // 目标值在左半部分，缩小右边界
                right = mid - 1;
            }
        }

        // 循环结束，left 即为插入位置
        return left;
    }

    // 方法二：递归版二分查找（补充，时间复杂度 O(log n)）
    // 核心思想：通过递归不断缩小搜索范围，逻辑与迭代版一致
    static int SearchInsertRecursive(int[] nums, int target)
    {
        return SearchInsertRecursiveHelper(nums, target, 0, nums.Length - 1);
    }

    // 递归辅助函数
    // nums：原始数组
    // target：目标值
    // left：当前搜索范围的左边界
    // right：当前搜索范围的右边界
    static int SearchInsertRecursiveHelper(int[] nums, int target, int left, int right)
    {
        // 终止条件：搜索范围为空，返回 left 作为插入位置
        if (left > right)
        {
            return left;
        }

        // 计算中间位置
        int mid = left + (right - left) / 2;

        if (nums[mid] == target)
        {
            // 找到目标值，直接返回索引
            return mid;
        }
        else if (nums[mid] < target)
        {
            // 目标值在右半部分，递归搜索 [mid+1, right]
            return SearchInsertRecursiveHelper(nums, target, mid + 1, right);
        }
        else
        {
            // 目标值在左半部分，递归搜索 [left, mid-1]
            return SearchInsertRecursiveHelper(nums, target, left, mid - 1);
        }
    }

    #endregion
}

35.4 运行结果

示例1 二分查找 方法 输入：[1,3,5,6], target=5 输出：2
示例1 递归二分 方法 输入：[1,3,5,6], target=5 输出：2
示例2 二分查找 方法 输入：[1,3,5,6], target=2 输出：1
示例2 递归二分 方法 输入：[1,3,5,6], target=2 输出：1
示例3 二分查找 方法 输入：[1,3,5,6], target=7 输出：4
示例3 递归二分 方法 输入：[1,3,5,6], target=7 输出：4
示例4 二分查找 方法 输入：[1,3,5,6], target=0 输出：0
示例4 递归二分 方法 输入：[1,3,5,6], target=0 输出：0
示例5 二分查找 方法 输入：[1], target=0 输出：0
示例5 递归二分 方法 输入：[1], target=0 输出：0
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏