leetcode35：搜索插入位置

题目链接

leetcode

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(logn) 的算法。

C++ 代码

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

/*
    二分，查找大于等于目标值的第一个位置。

    时间复杂度：O(logn)
    空间复杂度：O(1)
*/
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;

        // 搜索区间为 [left, right]，左闭右闭
        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < target) {
                // target 在右区间，变为 [mid+1, right]
                left = mid + 1;
            } else if (nums[mid] > target) {
                // target 在左区间，变为 [left, mid-1]
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 数组中找到目标值，直接返回下标
                return mid;
            }
        }

        // 处理如下四种情况
        // 目标值在数组所有元素之前，[0, -1]
        // 目标值等于数组中某一个元素，return mid
        // 目标值插入数组中的位置 [left, right]，return right + 1
        // 目标值在数组所有元素之后 [left, right]，因为是右闭区间，所以 return right + 1
        return right + 1;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {1,3,5,6},
        {1,3,5,6},
        {1,3,5,6}
    };
    vector<int> target_cases = {
        5, 2, 7
    };

    for (size_t i = 0; i < nums_cases.size(); i++) {
        auto& nums = nums_cases[i];
        int target = target_cases[i];
        int result = solution.searchInsert(nums, target);

        cout << "Input: nums = ";
        printArray(nums);
        cout << ", target = " << target << endl;
        cout << "Output: " << result << endl;
    }

    return 0;
}