在有序数组中查找元素的第一个和最后一个位置

在算法面试和实际工程开发中，在已排序数组中查找元素的边界是一个非常经典的问题。通常，我们会通过二分查找的变体来解决这个问题，其时间复杂度为 O(log n)。然而，站在 2026 年的开发视角，我们不仅要关注算法本身的正确性，更要思考如何在现代 AI 辅助的开发环境中编写高可维护性、鲁棒性极强的生产级代码。在这篇文章中，我们将深入探讨这一问题的多种解法，并结合现代技术趋势，分享我们在实际项目中的最佳实践。

问题的本质与工程挑战

让我们首先回顾一下问题的核心：给定一个可能包含重复元素的已排序数组 INLINECODE03aa4ab0，我们需要找到元素 INLINECODE0f30d65d 的第一次和最后一次出现的位置。如果未找到，则返回 {-1, -1}。

虽然这看起来是一个基础的算法题，但在海量数据处理（如日志分析、金融时序数据查询）的场景下，代码的执行效率和边界处理能力至关重要。我们需要确保代码不仅能处理常规数据，还能优雅地应对空数组、全相同元素数组以及目标元素不存在等极端情况。

现代开发范式下的解决方案

#### 1. 朴素方法：迭代遍历

在处理小规模数据或者为了快速验证原型时，线性扫描是最直观的方法。虽然它的时间复杂度是 O(n)，但在数据量不大（n < 100）的情况下，由于其极低的常数因子和简单的逻辑，往往能提供比二分查找更快的实际速度（避免了二分查找的分支预测开销）。

在编写这段代码时，我们建议采用 Vibe Coding（氛围编程） 的思路，即先通过自然语言描述逻辑，再让 AI 辅助生成基础代码，最后由人工进行 Code Review。以下是经过我们优化后的迭代版本，特别注重了循环的提前终止优化：

// 优化的线性扫描：找到最后一次出现后即可提前终止
vector findOptimized(vector& arr, int x) {
    int first = -1, last = -1;
    int n = arr.size();
    for (int i = 0; i  x) {
            // 剪枝优化：数组有序，如果当前元素已大于x，后续不可能再出现x
            break; 
        }
    }
    return {first, last};
}

#### 2. 预期方法：标准二分查找

当数据规模达到百万级以上时，O(log n) 的算法优势是决定性的。我们可以分别编写两个辅助函数 INLINECODEf13773d7 和 INLINECODE88505c74，或者编写一个通用的二分查找模板。

在生产环境中，我们通常会将二分查找封装为一个通用的模板函数，接受一个比较器，这样可以复用核心逻辑。以下是针对此问题的标准二分实现，我们在其中加入了详细的 断言检查，这在 AI 辅助调试过程中非常有用：

def find_first_occurrence(arr, x):
    low, high = 0, len(arr) - 1
    result = -1
    while low <= high:
        # 防止整数溢出（虽然在 Python 中不常见，但在 Java/C++ 中是必须考虑的）
        mid = low + (high - low) // 2
        
        if arr[mid] == x:
            result = mid
            # 关键点：即使找到了，我们也继续向左搜索，看是否还有更早的出现
            high = mid - 1
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
            
    return result

def find_last_occurrence(arr, x):
    low, high = 0, len(arr) - 1
    result = -1
    while low <= high:
        mid = low + (high - low) // 2
        
        if arr[mid] == x:
            result = mid
            # 关键点：即使找到了，我们也继续向右搜索
            low = mid + 1
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
            
    return result

def find_binary_search_approach(arr, x):
    # Python 中的海象运算符 := 使代码更加简洁
    if not arr: return [-1, -1]
    first = find_first_occurrence(arr, x)
    # 微优化：如果第一次都没找到，就不必找最后一次了
    if first == -1:
        return [-1, -1]
    last = find_last_occurrence(arr, x)
    return [first, last]

#### 3. 替代方案：利用语言内置库

到了 2026 年，现代编程语言的标准库已经极其强大。利用内置函数不仅可以减少代码量，还能利用底层优化（如 SIMD 指令集、JIT 优化）。

• C++: 使用 INLINECODEcade6e81 和 INLINECODE0f1ddf5d。这是我们最推荐的生产级写法，因为它经过了编译器厂商的极致优化。
• Java: 使用 Arrays.binarySearch。注意处理返回值的插入点问题。
• Python: 使用 bisect 模块。

以下是使用 C++ STL 的实现，展示了现代 C++ 的简洁与高效：

#include 
using namespace std;

vector findUsingSTL(vector& arr, int x) {
    // lower_bound 返回第一个 >= x 的元素的迭代器
    auto first_it = lower_bound(arr.begin(), arr.end(), x);
    
    // 检查是否越界或者该位置的值不等于 x
    if (first_it == arr.end() || *first_it != x) {
        return {-1, -1};
    }
    
    // upper_bound 返回第一个 > x 的元素的迭代器
    // 最后一次出现的位置就是 upper_bound - 1
    auto last_it = upper_bound(arr.begin(), arr.end(), x);
    
    int first = first_it - arr.begin();
    int last = last_it - arr.begin() - 1;
    
    return {first, last};
}

2026年开发视角下的深度反思

#### 性能监控与可观测性

在微服务架构中，我们通常会将此类搜索逻辑封装为一个独立的微服务或库。为了确保性能，我们不仅仅是写代码，还要注入 可观测性。

你可能会遇到这样的情况：在开发环境中运行良好，但在生产环境的高并发下出现延迟激增。这时，我们需要在代码中嵌入 Metric 记录。

import time
from bisect import bisect_left, bisect_right

def find_with_observability(arr, x):
    start_time = time.perf_counter()
    
    # 核心逻辑
    left = bisect_left(arr, x)
    right = bisect_right(arr, x)
    
    latency = (time.perf_counter() - start_time) * 1000 # 毫秒
    
    # 假设我们有一个全局的监控客户端
    # monitor.record_histogram(‘search.algorithm.latency‘, latency)
    if 0 <= left < len(arr) and arr[left] == x:
        return [left, right - 1]
    return [-1, -1]

#### Agentic AI 与结对编程

在使用像 Cursor 或 Windsurf 这样的 AI IDE 时，我们可以不仅仅是让 AI 生成代码，而是让它扮演“防守型程序员”的角色。

例如，我们可以这样与 AI 交互：“这是我的二分查找代码，请尝试构造一个包含重复元素、单元素数组以及目标不在数组中的测试用例，并检查我的代码是否存在整数溢出或死循环的风险。”

这种 Agentic AI 的工作流让我们在 2026 年能够以更少的精力写出更安全的代码。AI 不仅仅是补全变量，它成为了我们的安全网。

边界情况与容灾：我们的实战经验

在我们的一个涉及实时日志分析的项目中，我们遇到了一个棘手的问题：输入数组虽然是“逻辑上有序”的，但由于多线程并发写入，偶尔会出现微小的扰动。直接的二分查找在这种情况下会导致未定义行为。

我们的解决方案是引入“鲁棒性二分查找”：

• 限制迭代深度：虽然正常是 O(log n)，但加入一个计数器，如果循环次数超过 2 * log2(n) + 2，则强制终止，防止因数据错误导致的死循环。
• 后验检查：二分查找返回索引后，反向验证 arr[index] == x 是否成立。如果不成立，触发降级策略（如切换为线性扫描或报警）。

// Java 示例：带有安全检查的二分查找
public int[] findRobust(int[] arr, int x) {
    int low = 0, high = arr.length - 1;
    int first = -1, last = -1;
    double limit = Math.log(arr.length) / Math.log(2) * 2 + 4; // 安全阈值
    int iterations = 0;

    // 查找 First
    while (low  limit) {
            // 触发报警：数据可能损坏或算法出错
            System.err.println("Warning: Binary search exceeded safe iteration limit.");
            return new int[]{-1, -1}; // 或者降级为线性扫描
        }
        int mid = low + (high - low) / 2;
        if (arr[mid] == x) {
            first = mid;
            high = mid - 1;
        } else if (arr[mid] < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    // ... 查找 Last 逻辑类似，略 ...
    return new int[]{first, last};
}

总结：从算法到工程

这篇文章中，我们从“查找元素的第一个和最后一个位置”这个简单的算法问题出发，探讨了从 2026 年视角下的工程化实践。我们不仅实现了朴素方法和二分查找，还讨论了 STL 库的使用、AI 辅助开发流程以及生产环境下的容灾策略。

技术的演进不仅仅在于更快的 CPU 或更复杂的语言，更在于我们开发思维的转变。当我们编写代码时，我们不仅仅是在解决问题，更是在构建一个可维护、可观测、且具有韧性的系统。希望这些经验能帮助你在未来的项目中写出更卓越的代码。