Java如何在排序数组中查找元素的第一个和最后一个位置

在Java编程中，处理排序数组时，经常需要查找某个特定元素的第一个和最后一个位置。这种需求在二分查找算法中尤为常见，尤其是在处理重复元素的数组时。本文将详细介绍如何在Java中实现这一功能。

1. 问题描述

给定一个按照升序排列的整数数组 nums 和一个目标值 target，要求找到 target 在数组中的第一个和最后一个位置。如果 target 不存在于数组中，则返回 [-1, -1]。

例如： - 输入：nums = [5,7,7,8,8,10], target = 8 - 输出：[3, 4]

2. 解决思路

要解决这个问题，我们可以使用二分查找算法。由于数组是排序的，二分查找是一种高效的查找方法。我们需要找到 target 的第一个位置和最后一个位置，可以通过两次二分查找来实现：

1. 查找第一个位置：在二分查找过程中，当找到 target 时，继续在左半部分查找，直到找到第一个 target。
2. 查找最后一个位置：在二分查找过程中，当找到 target 时，继续在右半部分查找，直到找到最后一个 target。

3. 代码实现

以下是Java代码实现：

public class SearchRange {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1};
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        // 查找第一个位置
        int left = findFirst(nums, target);
        if (left == -1) {
            return result;
        }
        
        // 查找最后一个位置
        int right = findLast(nums, target);
        
        result[0] = left;
        result[1] = right;
        return result;
    }
    
    private int findFirst(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int first = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                first = mid;
                right = mid - 1; // 继续在左半部分查找
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return first;
    }
    
    private int findLast(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int last = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                last = mid;
                left = mid + 1; // 继续在右半部分查找
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return last;
    }
    
    public static void main(String[] args) {
        SearchRange solution = new SearchRange();
        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 8;
        int[] result = solution.searchRange(nums, target);
        System.out.println("[" + result[0] + ", " + result[1] + "]");
    }
}

4. 代码解析

4.1 findFirst 方法

• 初始化：left 和 right 分别指向数组的起始和结束位置。
• 循环条件：当 left <= right 时，继续查找。
• 中间位置：计算中间位置 mid。
• 判断：
  • 如果 nums[mid] == target，则更新 first 为 mid，并继续在左半部分查找（right = mid - 1）。
  • 如果 nums[mid] < target，则 left = mid + 1。
  • 如果 nums[mid] > target，则 right = mid - 1。

4.2 findLast 方法

• 初始化：left 和 right 分别指向数组的起始和结束位置。
• 循环条件：当 left <= right 时，继续查找。
• 中间位置：计算中间位置 mid。
• 判断：
  • 如果 nums[mid] == target，则更新 last 为 mid，并继续在右半部分查找（left = mid + 1）。
  • 如果 nums[mid] < target，则 left = mid + 1。
  • 如果 nums[mid] > target，则 right = mid - 1。

4.3 searchRange 方法

• 初始化：创建一个长度为2的数组 result，初始值为 [-1, -1]。
• 检查数组：如果数组为空或长度为0，直接返回 result。
• 查找第一个位置：调用 findFirst 方法，如果返回 -1，说明 target 不存在，直接返回 result。
• 查找最后一个位置：调用 findLast 方法。
• 返回结果：将 first 和 last 赋值给 result 并返回。

5. 总结

通过两次二分查找，我们可以在O(log n)的时间复杂度内找到目标元素的第一个和最后一个位置。这种方法在处理排序数组时非常高效，尤其是在数组中存在大量重复元素的情况下。希望本文能帮助你更好地理解如何在Java中实现这一功能。