在Java中查找数组的中间元素

1. 引言

本文将探讨如何查找数组的中间元素。数组是一种存储相同类型数据元素的数据结构。数组元素在内存中连续存储，并通过索引访问，且具有固定长度。

2. 问题描述

给定包含n个元素的数组，需要返回一个包含数组中间元素的新数组。 当输入数组长度为奇数时，存在一个中间元素；当长度为偶数时，则存在两个中间元素。

输出数组的长度应为1或2，具体取决于输入数组。示例：

输入数组[1, 2, 3, 4, 5]（长度5为奇数），输出[3]
输入数组[1, 2, 3, 4, 5, 6]（长度6为偶数），输出[3, 4]

需考虑边界情况：

空数组 → 输出空数组
长度1或2的数组 → 直接返回原数组

3. 使用数组操作查找中间元素

数组的length属性表示元素数量，元素通过0-based索引访问。

3.1. 奇数长度数组的中间元素

对于长度为n（奇数）的数组：

首索引为0，末索引为n-1
中间索引计算公式：(0 + (n-1)) / 2 → 简化为n/2

关键点：Java的整数除法会丢弃小数部分。例如长度为99的数组，中间索引为99/2 = 49（非49.5或50）。

int[] middleOfArray(int[] array) {
    int n = array.length;
    int mid = n / 2;
    return new int[] { array[mid] };
}

3.2. 偶数长度数组的中间元素

对于偶数长度数组，中间元素位于索引(n/2)-1和n/2。合并奇偶情况：

int[] middleOfArray(int[] array) {
    if (ObjectUtils.isEmpty(array) || array.length < 3) {
        return array;
    }
    int n = array.length;
    int mid = n / 2;
    if (n % 2 == 0) {
        int mid2 = mid - 1;
        return new int[] { array[mid2], array[mid] };
    } else {
        return new int[] { array[mid] };
    }
}

测试用例：

int[] array = new int[100];
for (int i = 0; i < array.length; i++) {
    array[i] = i + 1;
}
int[] expectedMidArray = { 50, 51 };
MiddleOfArray middleOfArray = new MiddleOfArray();
Assert.assertArrayEquals(expectedMidArray, middleOfArray.middleOfArray(array));

int[] expectedMidArrayForOddLength = { 50 };
Assert.assertArrayEquals(expectedMidArrayForOddLength, middleOfArray.middleOfArray(Arrays.copyOfRange(array, 0, 99)));

3.3. 指定范围内的中间元素

当需查找数组子集（由start和end定义）的中间元素时：

中间索引公式：mid = (start + end) / 2

⚠️ 踩坑警告：当start和end接近Integer.MAX_VALUE时，(start + end)可能溢出！
解决方案：改用mid = start + (end - start) / 2

int[] middleOfArrayWithStartEnd(int[] array, int start, int end) {
    int mid = start + (end - start) / 2;  // 防溢出
    int n = end - start;
    if (n % 2 == 0) {
        int mid2 = mid - 1;
        return new int[] { array[mid2], array[mid] };
    } else {
        return new int[] { array[mid] };
    }
}

3.4. 性能分析

✅ 数组访问是O(1)操作（内存连续，直接索引定位）
✅ 所有上述方法均为常数时间复杂度O(1)

4. 使用位运算查找中间元素

利用位运算替代除法运算：

**无符号右移运算符>>>**：等价于除以2的幂次方（a >>> n ≈ a / (2^n)）
优势：硬件底层实现，现代CPU执行更快

int[] middleOfArrayWithStartEndBitwise(int[] array, int start, int end) {
    int mid = (start + end) >>> 1;  // 无符号右移
    int n = end - start;
    if (n % 2 == 0) {
        int mid2 = mid - 1;
        return new int[] { array[mid2], array[mid] };
    } else {
        return new int[] { array[mid] };
    }
}

5. 数组的中位数

当数组元素为数值类型且已排序时，中间元素即为中位数（统计学重要指标）：

奇数长度 → 中间元素
偶数长度 → 两个中间元素的平均值

int medianOfArray(int[] array, int start, int end) {
    Arrays.sort(array); // 确保有序（实际应用中可能需优化）
    int mid = (start + end) >>> 1;
    int n = end - start;
    if (n % 2 == 0) {
        int mid2 = mid - 1;
        return (array[mid2] + array[mid]) / 2;
    } else {
        return array[mid];
    }
}

⚠️ 大数据场景：当数组无法全部加载到内存时（如全国房价数据），需改用流式处理方案（如堆结构计算数据流中位数）。

6. 总结

本文探讨了查找数组中间元素的多种方法：

基础数组操作：通过索引计算，注意整数除法和溢出问题
位运算优化：使用无符号右移提升性能
中位数扩展：适用于有序数值数组的统计场景

所有代码示例可在GitHub获取。

Persistence

REST

Security