Java泛型折半查找法实现与原理

Theo

发布时间：2026-10-16| 3人浏览过

原创

本文介绍如何在Java中利用泛型技术实现通用的折半查找算法。该方法要求数据集合有序且元素可比较，通过将搜索范围不断减半来实现高效查找，并提供了完整的Java代码示例与执行结果解析。

Java泛型化折半查找实现

第1步：定义折半查找逻辑与泛型约束

折半查找（Binary Search）是一种在有序数组中查找特定元素的高效算法。其核心思想是每次将搜索区间缩小一半。在使用泛型实现时，必须保证数组中的元素类型实现了 java.lang.Comparable 接口，以便进行大小比较。

算法步骤：

初始化边界：设置查找范围的下界 low=0 和上界 high=array.length-1。
计算中点：获取中间索引 mid = (low + high) / 2。
比较判断：

若目标值等于中点元素，则查找成功，返回 mid。
若目标值大于中点元素，说明目标在右半区，调整下界 low = mid + 1。
若目标值小于中点元素，说明目标在左半区，调整上界 high = mid - 1。

循环终止：当 low > high 时，表示查找范围已空，返回 -1 表示未找到。

第2步：编写Java泛型工具类

以下代码展示了 BinSearch 类的完整实现。关键点在于方法签名中的 <T extends Comparable<? super T>>，这限制了泛型类型必须具备可比性。

package com.xiaoxuzhu;

import java.util.Arrays;

public class BinSearch {

    /**
     * 泛型化的折半查找方法
     * @param array 已经排序的数组
     * @param key   要查找的目标元素
     * @return      目标元素的索引，未找到返回-1
     */
    public static <T extends Comparable<? super T>> int search(T[] array, T key) {
        int low = 0;
        int high = array.length - 1; // 修正原稿错误：上界应为 length-1
        int mid = 0;

        while (low <= high) {
            // 优化：防止大数相加导致的整型溢出
            mid = low + (high - low) / 2;

            // 使用 compareTo 进行比较
            int compareResult = key.compareTo(array[mid]);

            if (compareResult > 0) {
                // 目标值在中点右侧
                low = mid + 1;
            } else if (compareResult < 0) {
                // 目标值在中点左侧
                high = mid - 1;
            } else {
                // 找到目标
                return mid;
            }
        }
        return -1; // 未找到
    }

    public static void main(String[] args) {
        // 测试用例：Integer 数组
        Integer[] ints = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println("数据集合：" + Arrays.toString(ints));
        
        // 查找元素 3
        int index = search(ints, 3);
        System.out.println("元素3所对应的索引序号：" + index);
        
        // 查找不存在的元素 11
        int notFoundIndex = search(ints, 11);
        System.out.println("元素11所对应的索引序号：" + notFoundIndex);
    }
}

第3步：验证与注意事项

运行上述代码后，程序将输出查找到的索引值。对于整数数组，元素3位于索引2处。

重要修正与优化：

边界条件：原始草稿中 high 初始化为 array.length，这在标准二分查找中是错误的，会导致 ArrayIndexOutOfBoundsException。正确做法是 array.length - 1。
溢出防护：在计算中点时，(low + high) / 2 在数组极大时可能因整数溢出变成负数。推荐使用 low + (high - low) / 2。
比较方式：必须使用对象的 compareTo() 方法而非运算符，以适配字符串等引用类型。

相关知识点扩展

C/C++中的折半查找实现差异

在C语言中，由于缺乏原生泛型机制，通常通过指针和函数指针或模板特化来实现类似功能，或者针对特定类型（如int）编写专用函数。例如C语言版的核心逻辑如下：

#include<stdio.h>
#include<stdlib.h>

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int left = 0;
    int right = sizeof(arr) / sizeof(arr[0]) - 1;
    int key = 7;
    int mid = 0;

    while (left <= right)
    {
        // C语言常用位运算优化除法
        mid = (left + right) >> 1; 
        
        if (arr[mid] > key)
        {
            right = mid - 1;
        }
        else if (arr[mid] < key)
        {
            left = mid + 1;
        }
        else
        {
            break;
        }
    }

    if (left <= right)
    {
        printf("找到了，下标是%d\n", mid);
    }
    else
    {
        printf("找不到\n");
    }
    return 0;
}