二分查找篇——搜索插入位置【LeetCode】三种写法，python2/python3
35. 搜索插入位置
一、算法逻辑（逐步通顺讲解每一步思路）
这段代码的目的是：在一个 升序排列的数组 nums 中查找 target 应插入的位置，使得数组依然保持有序。若 target 存在，则返回其索引；若不存在，返回插入后该值应处的位置索引。
代码整体使用的是一个自定义实现的「lower_bound」二分查找函数：
✅ 1️⃣ 初始定义指针区间
-
left = 0，right = len(nums)，注意这里right是开区间（不包括数组最后一位索引）； -
区间
[left, right)表示搜索空间。
✅ 2️⃣ 循环条件 while left < right
只要搜索区间不为空（左指针小于右指针），就持续缩小范围。
✅ 3️⃣ 计算中点 mid = (left + right) // 2
标准二分方式，防止溢出。
✅ 4️⃣ 判断中点元素与目标值关系：
-
若
nums[mid] < target：说明目标值应该在mid+1到right之间，因此将left指针右移到mid + 1； -
否则（即
nums[mid] >= target）：目标值有可能是mid或在mid左边，将right指针左移到mid。
✅ 5️⃣ 最终返回 left（或 right）
循环结束时，left 一定指向第一个 大于等于 target 的位置，即 lower_bound。
这个值即为：
-
若
target存在，则是其位置； -
若不存在，则是应该插入的位置，仍然合法保持有序。
二、核心点总结
✅ 本质是对数组使用 左闭右开区间 [left, right) 的二分查找 模板。
✅ 核心目标是实现 lower_bound，即查找 第一个 >= target 的下标。
✅ while left < right + right = mid 模式是标准 lower_bound 实现技巧；
✅ 最终返回的是合法插入位置，可以统一处理「存在与否」。
class Solution:def searchInsert(self, nums: List[int], target: int) -> int:return lower_bound(nums, target)def lower_bound(nums:List[int], target:int) -> int:left = 0right = len(nums)while left<right:mid = (left+right)//2if nums[mid]<target:left = mid+1else:right = midreturn left # 或者right三、时间复杂度分析
每一轮循环都将搜索区间缩小一半，所以：
✅ 时间复杂度为 O(log n)，其中
n = len(nums)
四、空间复杂度分析
算法仅使用了常数个变量 (left, right, mid)，没有递归或额外数据结构：
✅ 空间复杂度为 O(1)
python2写法（包含闭区间、左闭右开区间和开区间三种写法）
# 闭区间写法
def lower_bound(nums, target):left, right = 0, len(nums) - 1 # 闭区间 [left, right]while left <= right: # 区间不为空# 循环不变量：# nums[left-1] < target# nums[right+1] >= targetmid = (left + right) // 2if nums[mid] < target:left = mid + 1 # 范围缩小到 [mid+1, right]else:right = mid - 1 # 范围缩小到 [left, mid-1]return left# 左闭右开区间写法
def lower_bound2(nums, target):left = 0right = len(nums) # 左闭右开区间 [left, right)while left < right: # 区间不为空# 循环不变量：# nums[left-1] < target# nums[right] >= targetmid = (left + right) // 2if nums[mid] < target:left = mid + 1 # 范围缩小到 [mid+1, right)else:right = mid # 范围缩小到 [left, mid)return left # 或者 right# 开区间写法
def lower_bound3(nums, target):left, right = -1, len(nums) # 开区间 (left, right)while left + 1 < right: # 区间不为空mid = (left + right) // 2# 循环不变量：# nums[left] < target# nums[right] >= targetif nums[mid] < target:left = mid # 范围缩小到 (mid, right)else:right = mid # 范围缩小到 (left, mid)return rightclass Solution(object):def searchInsert(self, nums, target):return lower_bound(nums, target) # 选择其中一种写法即可