当前位置：首页 > article >正文

LeetCode 热题 100_搜索插入位置（63_35_简单_C++）(二分查找)(”＞＞“ 与 “/”)

article 2025/2/22 21:11:39

LeetCode 热题 100_搜索插入位置（63_35）

- 题目描述：
- 输入输出样例：
- 题解：
- - 解题思路：
  - - 思路一（二分查找）：
  - 代码实现
  - - 代码实现（思路一（二分查找））：
    - 以思路一为例进行调试
    - 部分代码解读

题目描述：

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

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

提示：
1 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums 为无重复元素的升序排列数组
-10⁴ <= target <= 10⁴

题解：

解题思路：

思路一（二分查找）：

1、搜索插入位置，如果数组中之前存在与插入元素相同大小的元素，则之前元素的位置便是插入位置。如果之前不存在相同大小的元素，则插入到对应大小的位置。
2、具体思路如下：
我们每次查找取中间的元素与插入元素进行比对：
① 若中间元素等于插入元素则返回中间元素的下标。
② 若中间元素小于插入元素则插入元素的位置肯定在中间元素的右侧。
③ 若中间元素大于插入元素则插入元素的位置肯定在中间元素的左侧。
④ 依次进行查找，直到查找到对应位置。(二分查找结束没找到元素时，**左下标(left)**正好是插入的位置)

3、复杂度分析：
① 时间复杂度：O(logn)，其中n为数组的长度。（每次将搜索范围缩小一半）
② 空间复杂度：O(1)。使用常数空间存放若干变量。

代码实现

代码实现（思路一（二分查找））：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        // 初始化左右指针：left指向数组的开始，right指向数组的末尾
        int left = 0, right = nums.size() - 1, mid;
        
        // 使用二分查找算法，当 left <= right 时继续查找
        while (left <= right) {
            // 计算中间元素的索引，避免整数溢出
            mid = ((right - left) >> 1) + left;
            
            // 如果中间元素大于目标值，说明目标值在左半部分
            if (nums[mid] > target) {
                right = mid - 1;  // 调整右指针，缩小搜索范围到左半部分
            }
            // 如果中间元素小于目标值，说明目标值在右半部分
            else if (nums[mid] < target) {
                left = mid + 1;  // 调整左指针，缩小搜索范围到右半部分
            }
            // 如果中间元素等于目标值，直接返回中间元素的索引
            else {
                return mid;
            }
        }
        
        // 如果没有找到目标值，返回应该插入的位置，也就是 left 指针的位置
        return left;
    }
};

以思路一为例进行调试

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        // 初始化左右指针：left指向数组的开始，right指向数组的末尾
        int left = 0, right = nums.size() - 1, mid;
        
        // 使用二分查找算法，当 left <= right 时继续查找
        while (left <= right) {
            // 计算中间元素的索引，避免整数溢出
            mid = ((right - left) >> 1) + left;
            
            // 如果中间元素大于目标值，说明目标值在左半部分
            if (nums[mid] > target) {
                right = mid - 1;  // 调整右指针，缩小搜索范围到左半部分
            }
            // 如果中间元素小于目标值，说明目标值在右半部分
            else if (nums[mid] < target) {
                left = mid + 1;  // 调整左指针，缩小搜索范围到右半部分
            }
            // 如果中间元素等于目标值，直接返回中间元素的索引
            else {
                return mid;
            }
        }
        
        // 如果没有找到目标值，返回应该插入的位置，也就是 left 指针的位置
        return left;
    }
};


int main() {
    // 定义一个整数向量 nums，初始化为 {1, 3, 5, 6}
    vector<int> nums = {1, 3, 5, 6};
    
    // 定义目标值 target，设定为 5
    int target = 5;
    
    // 创建一个 Solution 类的对象 s
    Solution s;
    
    // 调用 searchInsert 方法，传入 nums 和 target，返回插入位置并输出
    // 该函数返回 target 的插入位置，如果已存在则返回目标值的索引
    cout << s.searchInsert(nums, target);
    
    return 0;
}