深入剖析二分查找：如何在有序数组中高效定位首尾元素

在这篇文章中，我们将深入探讨一个计算机科学中非常经典且基础，但又极具挑战性的算法问题。我相信你一定遇到过这样的情况：面对一个已经排好序的数组，我们需要快速找到一个给定元素的第一个和最后一个出现的位置。

这听起来似乎很简单，不是吗？但如果此时附加了一个严苛的条件——你的算法时间复杂度必须是 $O(\log n)$，简单的遍历整个数组（时间复杂度 $O(n)$）就不再适用了。别担心，我们将一起剖析这个问题，探索如何利用 二分查找 的变体来完美解决这一难题。无论你是正在准备面试，还是想在日常开发中优化代码性能，这篇文章都将为你提供详实的指导。

1. 问题的核心挑战与 2026 视角

首先，让我们明确一下问题的具体定义，确保我们在同一频道上。假设我们有一个按 非递减顺序 排序的整数数组 INLINECODE9113804d。我们的任务是找到一个给定的整数 INLINECODEc18839c6 在该数组中出现的 起始索引 和 结束索引。

在过去，我们可能只是为了解决算法题而学习它。但在 2026 年，随着数据量的爆炸式增长和 AI 辅助编程的普及，理解这种高效的查找逻辑变得尤为重要。想象一下，当我们处理数十亿级别的传感器数据流时，$O(n)$ 的算法可能会造成明显的延迟，而 $O(\log n)$ 则是实时的保证。这正是我们作为工程师在选择算法时必须具备的“性能敏感度”。

2. 算法思路深度解析：二分查找的“变奏曲”

提到 $O(\log n)$，标准 二分查找 是我们的首选。但标准二分查找有一个“毛病”：当有多个重复元素时，它返回的 mid 是不确定的。它可能返回中间的某一个目标值，而不一定是第一个或最后一个。因此，我们需要对标准算法进行 “魔改”。

我们可以将这个问题拆分为两个独立的子问题，分别编写两个函数：

• 寻找第一个出现的位置 (findFirst)
• 寻找最后一个出现的位置 (findLast)

#### 寻找第一个出现的位置 (findFirst)

我们的目标是找到 最左边 的目标值。

• 初始化 INLINECODE4c8055b3, INLINECODE11642d5b，result = -1。
• 当 low <= high 时，执行循环：

* 计算中间位置 mid = low + (high - low) / 2。

* 关键时刻：

如果 INLINECODEe986be35：这说明我们找到了 一个* 目标值。但这是第一个吗？不一定。为了寻找 第一个，我们不能直接返回，而应该先记录下这个位置 (INLINECODEf540eeb0)，然后 继续向左半部分搜索（即 INLINECODE46c52993）。为什么向左？因为我们需要看看左边还有没有更早出现的 INLINECODE6fef45b2。

* 如果 INLINECODE6578dd8c：说明目标在右侧，更新 INLINECODE5fa2de0f。

* 如果 INLINECODE35ca4356：说明目标在左侧，更新 INLINECODE907d5e2a。

#### 寻找最后一个出现的位置 (findLast)

逻辑与上面类似，只是方向相反。当我们找到 INLINECODEc0ddc476 时，记录位置，然后 向右半部分继续搜索（即 INLINECODEa2e5077d），以寻找更晚出现的 target。

3. 完整代码实现 (现代 C++ 风格)

让我们把上述逻辑转化为干净、高效的 C++ 代码。在 2026 年的代码规范中，我们更注重代码的“不可变性”和“明确性”。因此，尽管题目传入了数组长度 INLINECODE26a61afb，但在实现辅助函数时，我更倾向于使用 C++ 的 INLINECODE1346ee7d 或者明确界限的指针，以减少边界错误。为了兼容题目格式，我们保留数组写法，但加入详细注释。

#include 
#include 
#include 
using namespace std;

/**
 * 辅助函数：寻找 target 的第一个出现位置
 * 采用“左倾”二分策略：找到目标后不停止，而是继续压缩右边界
 */
int findFirst(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    int result = -1;
    
    while (low <= high) {
        // 防止溢出的写法，等同于 (low + high) / 2
        int mid = low + (high - low) / 2;
        
        if (arr[mid] == target) {
            result = mid;      // 记录当前候选位置
            high = mid - 1;    // 【核心逻辑】既然要找“第一个”，当前 mid 右边可以全部忽略
                              // 但 mid 左边可能还有，所以继续向左找
        }
        else if (arr[mid] < target) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    return result;
}

/**
 * 辅助函数：寻找 target 的最后一个出现位置
 * 采用“右倾”二分策略：找到目标后不停止，而是继续压缩左边界
 */
int findLast(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    int result = -1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        
        if (arr[mid] == target) {
            result = mid;      // 记录当前候选位置
            low = mid + 1;     // 【核心逻辑】既然要找“最后一个”，当前 mid 左边可以全部忽略
                              // 但 mid 右边可能还有，所以继续向右找
        }
        else if (arr[mid] < target) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    return result;
}

/**
 * 主函数：返回包含首尾位置的向量
 */
vector findOccurrences(int arr[], int n, int target) {
    int first = findFirst(arr, n, target);
    // 如果第一个都没找到，就没必要找最后一个了，直接返回[-1, -1]
    if (first == -1) return {-1, -1};
    
    int last = findLast(arr, n, target);
    return {first, last};
}

// 测试代码
int main() {
    int arr[] = {1, 2, 2, 2, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 2;
    
    vector result = findOccurrences(arr, n, target);
    cout << "First Occurrence: " << result[0] << endl;
    cout << "Last Occurrence: " << result[1] << endl;
    
    return 0;
}

4. 工程化实战：利用 STL 与 AI 辅助开发

在 2026 年，我们不再需要每次都手写这些底层逻辑。除非是在面试中考察你的基本功，否则在工程代码中，我们应该优先使用 C++ STL 提供的标准库函数。这不仅是代码简洁的问题，更是为了利用编译器厂商针对特定架构优化过的底层汇编代码。

#### STL 方案

我们利用 INLINECODE4fdae404 和 INLINECODEeed2a786 这两个神器：

#include 
#include 
#include 

vector findOccurrencesSTL(vector& arr, int target) {
    // 1. lower_bound: 找到第一个 >= target 的位置
    auto firstIt = lower_bound(arr.begin(), arr.end(), target);
    
    // 边界检查：如果越界 或者 该位置的值不等于 target（说明 target 不存在）
    if (firstIt == arr.end() || *firstIt != target) {
        return {-1, -1};
    }
    
    // 2. upper_bound: 找到第一个 > target 的位置
    auto lastIt = upper_bound(arr.begin(), arr.end(), target);
    
    // 最后一个出现的位置就在 upper_bound 的前一位
    int first = distance(arr.begin(), firstIt);
    int last = distance(arr.begin(), lastIt) - 1;
    
    return {first, last};
}

#### AI 辅助的最佳实践 (Agentic AI Workflow)

在我们的日常开发中，现在流行使用像 Cursor 或 GitHub Copilot 这样的 AI 辅助工具。对于上述二分查找逻辑，我们可以这样利用 AI 来提升效率并减少错误：

• Prompt Engineering（提示词工程）: 不仅仅是告诉 AI “写一个二分查找”，而是这样描述：“请使用 C++ STL 的 INLINECODEd5558516 实现一个函数，查找有序数组中 INLINECODEae82c147 的范围。请注意处理 INLINECODE3106c5b3 不存在的边界情况，并使用 INLINECODE9c3969b9 关键字简化迭代器声明。”
• Review and Refine（审查与重构）: AI 生成的代码可能逻辑正确，但可读性不一定符合团队规范。我们需要扮演“技术负责人”的角色，要求 AI 优化变量命名，或者增加 const 正确性检查。
• Testing with Edge Cases（边缘测试）: 让 AI 帮我们生成测试用例。例如：“生成一组包含空数组、全等于 target 的数组、以及 target 不存在的测试用例。”

这种“人类意图 + AI 实现 + 人类审查”的混合模式，正是 2026 年高效开发的核心竞争力。

5. 复杂度分析与现代性能调优

#### 时间与空间复杂度

• 时间复杂度: $O(\log n)$。无论是手写还是 STL，我们都只进行了常数次二分查找。
• 空间复杂度: $O(1)$。迭代法没有使用额外的栈空间。

#### CPU 缓存与分支预测视角

虽然 $O(\log n)$ 看起来很完美，但在现代 CPU 架构下，我们还需要考虑 缓存局部性。标准二分查找的优点是步数少，但因为跳跃性访问内存，可能会导致频繁的 Cache Miss。

• 对于小规模数据: 有时候简单的线性扫描配合 SIMD 指令集（单指令多数据）可能比二分查找更快，因为它可以充分利用 CPU 的流水线。
• 对于海量数据: 正如我们前面所述，$\log n$ 的优势无可撼动。如果数据量太大无法放入内存，我们可能需要考虑 B-Tree 或 LSM Tree 等磁盘友好的数据结构，但这已经超出了本题数组范畴。

6. 生产环境的陷阱与调试

在我们最近的一个实时数据分析项目中，有一个极其隐蔽的 Bug：当数组长度接近 INLINECODEc33a578a 类型的上限时，INLINECODE918e246b 发生了溢出，导致 mid 计算错误，程序直接崩溃。

解决方案： 这就是为什么我们在代码中强制使用 low + (high - low) / 2 的原因。这是一个教科书级的陷阱，但即使是资深工程师在疲劳时也容易忽略。
调试技巧： 使用 AddressSanitizer (ASan) 或 UndefinedBehaviorSanitizer (UBSan) 是 2026 年 C++ 开发的标准配置。它们能自动检测这种内存越界和未定义行为，比人眼审查可靠得多。

总结

通过这篇文章，我们不仅解决了“First and Last Occurrences”这个经典算法问题，还从工程实践、AI 辅助编程和底层性能优化的角度进行了全方位的复盘。

关键要点回顾：

• 找 第一个：遇到 INLINECODE6773d337 时，向左继续找 (INLINECODEe172f48e)。
• 找 最后一个：遇到 INLINECODE13742f3b 时，向右继续找 (INLINECODE96d42713)。
• 工程化思维：优先使用 STL，善用 AI 辅助，但必须保留底层原理的理解能力。
• 安全意识：警惕整数溢出，利用现代工具链进行防护。

希望这次探索对你有所帮助！无论你是独自在屏幕前 Coding，还是与 AI 结对编程，掌握这些基础逻辑都将是你构建复杂系统的坚实基石。编码愉快！