Hot100：Search Insert Position 排序数组中目标值插入位置的二分查找实战（LeetCode 35）

副标题 / 摘要
Search Insert Position 是二分查找的「Hello World」级题目：返回目标值在有序数组中的插入位置（存在返回下标，不存在返回应插入的下标）。本文用统一的 lower_bound 模板，把这个问题讲清楚，并展示其在日志、配置和策略表中的工程应用。

预计阅读时长：8~10 分钟
适用场景标签：二分查找入门、插入位置、范围查找
SEO 关键词：search insert position, lower_bound, 二分插入, 排序数组插入位置, LeetCode 35, Hot100

目标读者与背景

目标读者

知道二分查找基本原理，但还没形成自己的模板的同学；
在工程中经常对有序列表做插入 / 查找操作的后端 / 前端开发者；
刚开始刷 LeetCode，想用一道题把「下界二分」吃透的人。

为什么这题重要？

它是 most basic 的「lower_bound」模型：
- 第一个大于等于目标值的下标。
理解它之后：
- 起始位置 / 插入位置 / 统计 ≤ / ≥ 某值数量等，都可以统一用同一个模板。
在工程中：
- 策略阈值表、时间戳列表、版本列表等，都会用到类似逻辑。

A — Algorithm（题目与算法）

题目重述

给定一个按非降序排序的整数数组 nums 和一个目标值 target。
请在数组中搜索 target，如果存在则返回其下标；
如果不存在，则返回它按顺序插入时应该在的位置。
要求算法时间复杂度为 O(log n)。

输入

nums: 已排序（非降序）的整数数组，长度为 n
target: 目标整数

输出

整数：目标值的下标，若不存在则为应插入位置的下标

示例 1

nums   = [1, 3, 5, 6]
target = 5

数组中存在 5，且 nums[2] == 5，因此：

输出：2

示例 2

nums   = [1, 3, 5, 6]
target = 2

2 不在数组中：

1 之后，3 之前插入能保持有序；
插入位置下标为 1。

输出：1

示例 3

nums   = [1, 3, 5, 6]
target = 7

7 大于数组中所有元素，应插入到末尾，位置为下标 4。

输出：4

示例 4

nums   = [1, 3, 5, 6]
target = 0

0 小于数组中所有元素，应插入到开头，位置为下标 0。

输出：0

C — Concepts（核心思想）

1. Search Insert Position 本质是什么？

题意中的“存在则返回下标，不存在则返回插入位置”，可以统一为：

返回数组中第一个大于等于 target 的位置。

这就是典型的：

下界（Lower Bound） 问题：

lower_bound(nums, target)
  = min i, 使得 nums[i] >= target
  = 若不存在这样的 i，则返回 n

这一点非常关键：
不需要区分“存在”与“不存在”，一个 lower_bound 全搞定。

2. 下界二分模板（左闭右开区间）

统一用 [l, r) 写法：

l = 0, r = n
while (l < r):
    mid = (l + r) // 2
    if nums[mid] >= target:
        r = mid
    else:
        l = mid + 1
return l

返回值 l 有三种情况：

0 <= l < n 且 nums[l] == target → 数组中存在 target，插入位置就是这个下标；
0 <= l < n 且 nums[l] > target → 应插入到 l 位置，才能保持有序；
l == n → target 大于所有元素，应插入到末尾（下标 n）。

这与题目要求完全一致，无需额外判断。

3. 算法类型与复杂度

算法类型：二分查找（lower_bound）
性质：单调性 + 有序数组 + 边界查找
时间复杂度：O(log n)
空间复杂度：O(1)

实践指南 / 实现步骤

初始化搜索区间
- 设 l = 0, r = n（左闭右开）。
循环直到收敛

while l < r:
    mid = (l + r) // 2
    if nums[mid] >= target:
        r = mid
    else:
        l = mid + 1

返回结果
- 循环结束时，l == r，它们都等于第一个满足 nums[i] >= target 的下标；
- 直接返回 l 即为答案，符合题目“存在则返回位置，不存在则为插入位置”的定义。
边界验证
- nums 为空：n == 0 → l = 0, r = 0，直接返回 0，表示插入到位置 0；
- target 小于所有元素：最终 l == 0；
- target 大于所有元素：最终 l == n。

E — Engineering（工程应用）

Search Insert Position 这种“有序数组 + 插入位置”需求，在工程里非常常见。

场景 1：灰度发布阈值表（Python）

背景
你有一个按流量比例排序的灰度阈值列表，例如：

thresholds = [10, 30, 60, 100]  # 单位：百分比

想根据一个随机数 x（1~100）找到它属于哪个灰度段：

x <= 10 → A 版本
10 < x <= 30 → B 版本
…

你可以用 Search Insert Position 找到 x 对应的插入位置，间接确定灰度桶。

示例代码

from typing import List


def search_insert(nums: List[int], target: int) -> int:
    l, r = 0, len(nums)
    while l < r:
        mid = (l + r) // 2
        if nums[mid] >= target:
            r = mid
        else:
            l = mid + 1
    return l


if __name__ == "__main__":
    thresholds = [10, 30, 60, 100]
    for x in [5, 10, 25, 70, 101]:
        idx = search_insert(thresholds, x)
        print(x, "-> insert index", idx)

场景 2：交易撮合 / 策略表查找（Go）

背景
在交易或风控系统中，经常会维护一张按金额 / 风险值排序的策略表。例如：

amounts = [1000, 5000, 10000, 50000]

根据订单金额 order_amount，需要找到它应该落到哪个档位，从而读取对应策略参数。

示例代码（Go）

package main

import "fmt"

func searchInsert(nums []int, target int) int {
	l, r := 0, len(nums)
	for l < r {
		mid := l + (r-l)/2
		if nums[mid] >= target {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return l
}

func main() {
	amounts := []int{1000, 5000, 10000, 50000}
	for _, order := range []int{500, 1000, 2000, 20000, 80000} {
		idx := searchInsert(amounts, order)
		fmt.Println(order, "-> slot index", idx)
	}
}

场景 3：前端时间线 / 版本线高亮（JavaScript）

背景
前端页面上展示一个时间线或版本线（例如版本号：[1, 3, 5, 7]），需要高亮“当前版本”或“即将生效的版本”：

找到第一个 ≥ 当前版本号的节点；
或者判断当前版本是否恰好在数组中。

示例代码

function searchInsert(nums, target) {
  let l = 0, r = nums.length;
  while (l < r) {
    const mid = (l + r) >> 1;
    if (nums[mid] >= target) r = mid;
    else l = mid + 1;
  }
  return l;
}

console.log(searchInsert([1, 3, 5, 6], 5)); // 2
console.log(searchInsert([1, 3, 5, 6], 2)); // 1
console.log(searchInsert([1, 3, 5, 6], 7)); // 4
console.log(searchInsert([1, 3, 5, 6], 0)); // 0

R — Reflection（反思与深入）

1. 复杂度分析

每次循环把搜索区间 [l, r) 的长度缩小一半；
循环次数约为 log₂(n)；
时间复杂度：O(log n)；
空间复杂度：O(1)。

满足题目要求，也是工程上对有序数组查找的最佳常用复杂度。

2. 替代方案与常见错误

线性扫描（不推荐）

从头到尾遍历数组，找到第一个 nums[i] >= target 的位置 i；
时间复杂度 O(n)，在 n 很大时不够高效；
虽然实现简单，但不满足面试 / 高性能场景对 O(log n) 的要求。

错误二分写法 1：只找 “== target”

if nums[mid] == target: return mid

找到 target 时直接返回，但没处理「不存在」时插入位置的逻辑；
一般需要再写额外判断，使得代码冗长且容易遗漏边界。

错误二分写法 2：区间与条件混乱

左闭右开 / 左闭右闭混用，容易造成死循环；
条件 >= / > 写错，导致返回的不是下界。

当前方案优势

只关注 “第一个 >= target 的位置”，逻辑简单；
不区分“存在 / 不存在”，统一通过返回位置表达；
作为 lower_bound 模板，可复用于大量类似问题。

3. 与其他二分问题的关系

Search Insert Position 是二分查找题目族中最基础的一个：

本题：返回 lower_bound(target)；
Search Range 起始位置：同样是 lower_bound(target)；
Search Range 结束位置：是 upper_bound(target) - 1；
统计 < target 或 >= target 的数量：也可以通过 lower_bound / upper_bound 计算。

换句话说：

掌握好这一题的写法，就等于掌握了半个二分查找专题。

S — Summary（总结）

Search Insert Position 的本质是寻找第一个大于等于 target 的下标，即 lower_bound。
用统一的下界二分模板，可以在 O(log n) 时间内稳定求解。
只要坚持一种区间写法（如 [l, r)），很多二分边界问题都会变得很自然。
这道题在工程实践中对应于灰度阈值、策略表、时间线 / 版本线等多种“有序表插入位置”的需求。
通过本题，你可以为后续的 Search Range、最大正负数计数、旋转数组搜索等题打下坚实的二分基础。

参考与延伸阅读

LeetCode 35. Search Insert Position（原题）
LeetCode 34. Find First and Last Position of Element in Sorted Array
标准库中的 lower_bound / bisect_left / sort.Search 文档
二分查找专项题单（搜索插入位置、求平方根、旋转数组、峰值元素等）

多语言完整实现（Python / C / C++ / Go / Rust / JS）

Python 实现

from typing import List


def search_insert(nums: List[int], target: int) -> int:
    l, r = 0, len(nums)
    while l < r:
        mid = (l + r) // 2
        if nums[mid] >= target:
            r = mid
        else:
            l = mid + 1
    return l


if __name__ == "__main__":
    print(search_insert([1, 3, 5, 6], 5))  # 2
    print(search_insert([1, 3, 5, 6], 2))  # 1

C 实现

#include <stdio.h>

int searchInsert(int *nums, int numsSize, int target) {
    int l = 0, r = numsSize;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] >= target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

int main(void) {
    int nums[] = {1, 3, 5, 6};
    int n = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", searchInsert(nums, n, 5)); // 2
    printf("%d\n", searchInsert(nums, n, 2)); // 1
    printf("%d\n", searchInsert(nums, n, 7)); // 4
    printf("%d\n", searchInsert(nums, n, 0)); // 0
    return 0;
}

C++ 实现

#include <bits/stdc++.h>
using namespace std;

int searchInsert(vector<int> &nums, int target) {
    int l = 0, r = (int)nums.size();
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] >= target) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main() {
    vector<int> nums{1, 3, 5, 6};
    cout << searchInsert(nums, 5) << endl; // 2
    cout << searchInsert(nums, 2) << endl; // 1
    cout << searchInsert(nums, 7) << endl; // 4
    cout << searchInsert(nums, 0) << endl; // 0
    return 0;
}

Go 实现

package main

import "fmt"

func searchInsert(nums []int, target int) int {
	l, r := 0, len(nums)
	for l < r {
		mid := l + (r-l)/2
		if nums[mid] >= target {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return l
}

func main() {
	fmt.Println(searchInsert([]int{1, 3, 5, 6}, 5)) // 2
	fmt.Println(searchInsert([]int{1, 3, 5, 6}, 2)) // 1
}

Rust 实现

fn search_insert(nums: &[i32], target: i32) -> i32 {
    let mut l = 0usize;
    let mut r = nums.len();
    while l < r {
        let mid = l + (r - l) / 2;
        if nums[mid] >= target {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    l as i32
}

fn main() {
    let nums = vec![1, 3, 5, 6];
    println!("{}", search_insert(&nums, 5)); // 2
    println!("{}", search_insert(&nums, 2)); // 1
}

JavaScript 实现

function searchInsert(nums, target) {
  let l = 0, r = nums.length;
  while (l < r) {
    const mid = (l + r) >> 1;
    if (nums[mid] >= target) r = mid;
    else l = mid + 1;
  }
  return l;
}

console.log(searchInsert([1, 3, 5, 6], 5)); // 2
console.log(searchInsert([1, 3, 5, 6], 2)); // 1
console.log(searchInsert([1, 3, 5, 6], 7)); // 4
console.log(searchInsert([1, 3, 5, 6], 0)); // 0

行动号召（CTA）

把本文的 search_insert 实现记进你的「二分查找模板」，并尝试背下来（尤其是条件和区间写法）。
选一到两道需要统计 <= x 或 >= x 数量的题，试着用 lower_bound 模板来解决。
回顾你项目里的「有序表插入 / 定位」逻辑，看是否能用 Search Insert Position 思路让代码更简洁、更好维护。

目标读者与背景#

A — Algorithm（题目与算法）#

题目重述#

示例 1#

示例 2#

示例 3#

示例 4#

C — Concepts（核心思想）#

1. Search Insert Position 本质是什么？#

2. 下界二分模板（左闭右开区间）#

3. 算法类型与复杂度#

实践指南 / 实现步骤#

E — Engineering（工程应用）#

场景 1：灰度发布阈值表（Python）#

场景 2：交易撮合 / 策略表查找（Go）#

场景 3：前端时间线 / 版本线高亮（JavaScript）#

R — Reflection（反思与深入）#

1. 复杂度分析#

2. 替代方案与常见错误#

3. 与其他二分问题的关系#

S — Summary（总结）#

参考与延伸阅读#

多语言完整实现（Python / C / C++ / Go / Rust / JS）#

Python 实现#

C 实现#

C++ 实现#

Go 实现#

Rust 实现#

JavaScript 实现#

行动号召（CTA）#