题目

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

请必须使用时间复杂度为 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 <= 104
• -104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 104

解答

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int i = 0;
        while (i < nums.size() && nums[i] < target) {
            i++;
        }
        return i;
    }
};

• 定义一个变量 i 并初始化为 0，这个 i 用于遍历数组。
• 进入一个循环，只要 i 小于数组的长度并且当前 nums[i] 小于目标值 target，就执行循环体。在循环体中，将 i 的值加 1，这意味着不断向右移动指针，直到找到一个位置 i，使得 nums[i] 不小于目标值 target 或者已经遍历完整个数组。
• 最后，返回的 i 就是目标值应该插入的位置。如果在遍历过程中找到了等于目标值的元素，那么此时 i 就是该元素的索引；如果没有找到，那么 i 就是目标值应该插入以保持数组有序的位置。

这种方法虽然不是严格意义上的二分查找，但在这个特定场景下也能以相对高效的方式找到目标值或其插入位置。