Day 17。
今天两道题分别是 Find First and Last Position of Element in Sorted Array 和 Search Insert Position。
这两题都属于非常经典的 有序数组查找题。

今天的关键词：有序数组、边界查找、线性扫描、二分意识、插入位置。

🧠 LeetCode 34 – Find First and Last Position of Element in Sorted Array

💡 思路总结

这题要求在一个有序数组中，找到目标值第一次出现和最后一次出现的位置。

你的做法是直接扫描整个数组：

  • 第一次遇到 target 时，记录 first_pos
  • 后面继续遇到 target，不断更新 last_pos
  • 最后返回 [first_pos, last_pos]

这个思路很直接，也很好理解。

💻 代码实现

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty())return {-1,-1};
        vector<int> result;
        int first_pos = -1;
        int last_pos = -1;
        int count = 0;
        for(int i = 0;i<nums.size();i++){
            if(nums[i] == target && count == 0){
                first_pos = i;
                last_pos = i;
                count++;
            }
            else if(nums[i] == target && count != 0){
                last_pos = i;
                count++;
            }
        }
        result.push_back(first_pos);
        result.push_back(last_pos);  
        return result;
    }
};

📌 知识点总结

1️⃣ 线性扫描能做出来

你这题的写法本质上就是：

从左到右扫一遍，顺手维护首尾位置

如果只是为了做出来，这样完全没问题，逻辑也清楚。

2️⃣ count 的作用

你这里用了 count 来区分：

  • 是不是第一次遇到目标值

第一次命中时：

first_pos = i;
last_pos = i;

后面再命中时，只更新：

last_pos = i;

这个思路没有问题。

3️⃣ 这题真正想练的是“边界二分”

不过这题题目本身因为数组是有序的，其实更希望你想到：

用二分分别找左边界和右边界

因为线性扫描时间复杂度是 O(n)，
而二分可以做到 O(log n)。

所以这题真正的高频知识点不是“遍历找答案”，而是：

  • 左边界查找
  • 右边界查找
  • 二分找边界

✅ 你的写法可以再简化一点

其实你这里的 count 不是必须的。
可以更直接一点：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int first_pos = -1, last_pos = -1;

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == target) {
                if (first_pos == -1) first_pos = i;
                last_pos = i;
            }
        }

        return {first_pos, last_pos};
    }
};

这样会更紧凑。

✅ 更标准的二分解法思路

如果博客里想顺带提升一下，可以提一句：

  • 先二分找第一个 >= target 的位置
  • 再二分找第一个 > target 的位置
  • 两者组合出左右边界

这才是这题更经典的方向。

🔍 LeetCode 35 – Search Insert Position

💡 思路总结

这题要求在有序数组中找到目标值的位置。
如果目标不存在，就返回它应该插入的位置。

你的做法也是线性扫描：

  • 如果当前元素大于 target，说明应该插在当前位置
  • 如果当前元素等于 target，直接返回当前下标
  • 如果都没遇到，就说明应该插到数组末尾

这个思路同样很直观。

💻 代码实现

#include <queue>
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        queue<int> q;
        int result = 0;
        for(int i = 0;i<nums.size();i++){
            if(nums[i] > target)return result;
            else{
                if(nums[i] == target)return i;
                result++;
            }

        }
        return result;

    }
};

📌 知识点总结

1️⃣ 线性思路很好理解

你的逻辑可以概括成：

  • 当前数比目标大，插这里
  • 当前数等于目标，返回这里
  • 一直没找到，就插最后

对于理解题意来说，这种写法很适合入门。

2️⃣ result 其实就是插入位置

你这里的 result 本质上就是：

当前已经走过了多少个“小于等于插入前位置”的元素

所以最后返回 result，就得到了答案。

3️⃣ 这里的 queue<int> q; 是多余的

你代码里这一句：

queue<int> q;

其实完全没用到，可以删掉。

也就是说，更干净的版本应该是：

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

4️⃣ 这题本质上也是二分题

因为数组有序，所以最经典的解法其实也是二分。

这题很重要的一点在于：

插入位置，本质上就是“第一个大于等于 target 的位置”

这就是典型的 lower_bound 思想。

🧩 两题放在一起看

今天这两题虽然你都用了线性扫描，但它们其实都在指向同一个核心：

有序数组里，最重要的不只是“找值”，更是“找边界”

题目本质
LeetCode 34找 target 的左右边界
LeetCode 35找第一个大于等于 target 的位置

🧠 今日收获

今天最值得记住的两个模型：

1. 有序数组查找题

看到“数组有序”时，脑子里要立刻冒出来：

  • 能不能二分
  • 是找值，还是找边界
  • 是不是 lower_bound / upper_bound

2. 边界比值本身更重要

很多题表面看是在找某个数，实际上更关键的是：

  • 第一个等于它的位置
  • 最后一个等于它的位置
  • 第一个大于等于它的位置
  • 第一个大于它的位置

这就是边界查找思想。

💬 写给自己的话

Day 17 了。

你现在已经开始碰到一些很典型的“同类题”了。
这种题最有价值的地方就在于：

  • 表面题意不同
  • 但底层模型很像

今天这两题就是这样。
你虽然先用了线性扫描做出来，这很好，因为说明你先把题意吃透了。
接下来更重要的，是慢慢培养一种感觉：

看到有序数组，就优先想到二分和边界。

这种意识一旦建立起来，你后面做题会轻松很多。

继续坚持。
你现在已经不是单纯在刷题了，而是在一点一点训练自己的“题型雷达”。

阿玉，Day 17，继续冲。

—— 刷题第 17 天