LeetCode 35. 搜索插入位置 | C 二分查找最优解 题目描述题目级别简单给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。请必须使用时间复杂度为O(log⁡n)O(\log n)O(logn)的算法。 解题思路二分查找 (寻找下界)题目要求时间复杂度必须为O(log⁡n)O(\log n)O(logn)且数组是有序的这正是二分查找的经典应用场景。这道题的本质并不是单纯地“找目标值”而是寻找**“第一个大于等于 target 的元素位置”**也就是 C STL 中的lower_bound逻辑。如果找到了目标值这个位置就是目标值的索引。如果没找到目标值这个位置恰好就是它按顺序应该插入的位置。核心边界细节拆解很多新手写二分查找容易陷入死循环这道题的模板非常值得背诵记忆区间定义我们定义搜索区间为左闭右开[0, nums.size())。注意右边界r nums.size()为什么不是nums.size() - 1因为如果target比数组里的所有数都要大它理应被插入到数组的最末尾即索引为nums.size()的位置。把r设为nums.size()就能把这个越界插入的位置包含进搜索空间里。循环条件使用while (l r)。当l r时循环结束此时l或r就是我们要找的插入位置。状态转移计算中点int mid (l r) / 2;如果nums[mid] target说明目标值可能在mid的左边或者就是mid本身。因此将搜索区间缩小为左半部分即r mid;。如果nums[mid] target说明目标值严格大于中点元素必然在mid的右边。因此将搜索区间缩小为右半部分即l mid 1;。 C 代码实现classSolution{public:intsearchInsert(vectorintnums,inttarget){// 左边界 l 初始化为 0// 右边界 r 初始化为 nums.size()预留出插在数组末尾的可能性intl0,rnums.size();// 当 l r 时跳出循环锁定最终位置while(lr){intmid(lr)/2;// 如果 mid 处的值大于等于目标值说明插入位置在 mid 及其左侧if(nums[mid]target){rmid;}// 否则说明插入位置在 mid 的右侧else{lmid1;}}// 最终 l 和 r 相遇的地方就是目标位置returnl;}};