如何在有序数组中高效查找目标元素的首次与末次出现位置-java教程-PHP中文网

如何在有序数组中高效查找目标元素的首次与末次出现位置

本文详解使用二分查找在有序数组中定位目标值首次和末次出现索引的完整实现，涵盖方法重载设计、边界处理技巧及常见编译错误修复（如参数不匹配问题）。

本文详解使用二分查找在有序数组中定位目标值首次和末次出现索引的完整实现，涵盖方法重载设计、边界处理技巧及常见编译错误修复（如参数不匹配问题）。

在有序数组中查找某元素的首次出现位置（leftmost index） 和末次出现位置（rightmost index） 是经典二分搜索变体问题。由于数组已排序，暴力遍历（O(n)）非最优解；而标准二分仅能定位任意一个匹配位置，无法区分重复元素的边界。因此，需对二分逻辑进行定向调整：一次向左收缩搜索区间以锁定首个目标，另一次向右收缩以锁定最后一个目标。

核心思路是复用同一套二分框架，通过布尔标志 findStart 控制搜索方向：

当 findStart == true 时，命中 nums[mid] == target 后继续向左（end = mid - 1），确保不遗漏更左侧的相同值；
当 findStart == false 时，命中后向右（start = mid + 1），寻找最右边界。

但关键在于 LeetCode 的测试入口方法签名固定为 searchRange(int[] nums, int target)（双参数），而你的实现中该方法名为 search，且 searchRange 方法本身接收三参数——这导致编译器在调用时找不到匹配的 searchRange(int[], int) 方法，报错 actual and formal argument lists differ in length。

✅ 正确做法是：将双参数入口方法命名为 searchRange，并保留三参数辅助方法作为重载。Java 支持方法重载，这样既满足平台调用契约，又保持内部逻辑清晰。

以下是修正后的完整可提交代码：

class Solution {
    // LeetCode 要求的入口方法：双参数
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        result[0] = searchRange(nums, target, true);   // 查找首次出现
        result[1] = searchRange(nums, target, false);  // 查找末次出现
        return result;
    }

    // 辅助二分方法：三参数，支持方向控制
    private int searchRange(int[] nums, int target, boolean findStart) {
        int ans = -1;
        int start = 0;
        int end = nums.length - 1;

        while (start  nums[mid]) {
                start = mid + 1;
            } else {
                ans = mid; // 记录当前匹配位置
                if (findStart) {
                    end = mid - 1; // 继续向左找更早出现
                } else {
                    start = mid + 1; // 继续向右找更晚出现
                }
            }
        }
        return ans;
    }
}

? 注意事项与最佳实践：