力扣35题 解题思路和步骤 C++代码实现,力扣一共多少题

力扣35题要求在一个有序无重复元素的整数数组中，找到目标值应该插入的位置索引。给定数组nums和target，当target存在于数组中时返回其索引，不存在时返回按顺序插入的位置。该问题的本质是寻找第一个大于等于目标值的元素位置，这提示我们需要使用时间复杂度为O(log n)的二分查找算法。如何理解这个问题的特殊要求？假设给定数组为[1,3,5,6]，当target=5时直接返回索引2，而当target=2时则需要返回插入位置1。这种需求决定了我们的算法必须精确处理三种边界情况：目标值存在于数组首元素前、存在于数组中间位置、位于数组末尾之后。值得注意的是，题目中的有序数组条件为二分查找提供了应用前提。

二分查找算法设计原理

二分查找的核心在于通过不断缩小搜索范围来定位目标值。对于力扣35题，我们需要确定左闭右闭区间[left, right]的初始值，通常设置为left=0、right=nums.size()-1。关键点在于循环条件的设定和中点计算方式，这直接影响着边界条件的处理。为什么选择左闭右闭区间？这种设定可以避免索引越界问题，同时保证所有元素都被覆盖。每次循环计算mid=left+(right-left)/2可以防止整数溢出。当nums[mid]小于target时，说明目标值在右半区，需要将left更新为mid+1；反之则将right调整为mid-1。这种调整方式确保搜索区间能正确缩小。

模拟操作步骤：

1.输入nums=[1,3,5,6], target=2

2.初始状态left=0，right=3。

3.第一次循环mid=(0+3)/2=1，nums[1]=3>2，更新right=0。

4.此时mid=(0+0)/2=0，nums[0]=1<2，更新left=1。

5.循环终止后返回left值1，这是正确的插入位置。

在实现过程中要特别注意循环终止条件。当left>right时跳出循环，此时left指向的位置就是待插入的索引。

C++代码实现

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

时间复杂度与算法对比

该算法的时间复杂度为O(log n)，空间复杂度O(1)，是处理有序数组查找问题的最优解。与线性遍历的O(n)时间复杂度相比，在处理大规模数据时优势明显。当数组长度为10^6时，二分查找仅需20次循环即可完成定位，而线性扫描可能需要百万次操作。与STL库函数lower_bound的实现有何不同？C++标准库中的lower_bound函数同样采用二分查找，但通过迭代器实现。我们的自定义实现更便于理解底层逻辑，且避免了模板编程的复杂性。两者的时间复杂度相同，但自定义实现的内存占用更优。