如何在自定义泛型SortedArrayList ADT中手动实现二分搜索？

首先得明确一个关键前提：二分搜索的有效性完全依赖于列表已经按照你要搜索的关键字（这里是学生姓名）有序排列。如果你的SortedArrayList当前是按其他字段（比如学号）排序的，那直接按姓名做二分搜索肯定会出错，这一点一定要先确认。

接下来解决你提到的两个核心问题：泛型限制无法访问Student属性，以及二分方法的参数设计，这里有两种非常实用的方案：

方案一：使用关键字提取器（Function接口）传递比较逻辑 #

这种方式更直观，适合你明确知道要按某个字段（比如姓名）搜索的场景。我们可以给二分方法传入两个参数：

• 要搜索的目标关键字（比如String targetName）
• 一个函数，用来从泛型元素中提取出用于比较的关键字（比如从Student实例中提取姓名的Student::getFullName）

方法定义 #

在你的泛型SortedArrayList<E>中添加如下方法：

import java.util.function.Function;

public class SortedArrayList<E> implements SortedListInterface<E> {
    // 你的现有代码...

    // 泛型二分搜索方法，支持按任意可比较的关键字搜索
    public <K extends Comparable<? super K>> int binarySearch(K targetKey, Function<? super E, K> keyExtractor) {
        int low = 0;
        int high = size() - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // 避免整数溢出
            E midElement = get(mid); // 假设你的ADT有get(int index)方法获取元素
            K midKey = keyExtractor.apply(midElement);

            int compareResult = midKey.compareTo(targetKey);
            if (compareResult == 0) {
                return mid; // 找到目标，返回索引
            } else if (compareResult < 0) {
                low = mid + 1; // 目标在右半区
            } else {
                high = mid - 1; // 目标在左半区
            }
        }
        return -1; // 未找到返回-1，或者可以返回-(low+1)表示插入位置，类似Java内置API
    }
}

调用示例 #

当你需要按姓名搜索时，直接传入目标姓名和提取姓名的方法引用：

SortedArrayList<Student> studentList = new SortedArrayList<>();
// 假设studentList已经按姓名升序排列好
int index = studentList.binarySearch("张三", Student::getFullName);
if (index != -1) {
    Student foundStudent = studentList.get(index);
    // 处理找到的学生
}

方案二：使用比较器（Comparator接口）传递比较逻辑 #

这种方式更灵活，适合需要自定义比较规则的场景（比如忽略大小写的姓名搜索）。方法接收目标元素和一个比较器，用比较器来判断目标和列表元素的大小关系。

方法定义 #

import java.util.Comparator;

public class SortedArrayList<E> implements SortedListInterface<E> {
    // 你的现有代码...

    public int binarySearch(E target, Comparator<? super E> comparator) {
        int low = 0;
        int high = size() - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            E midElement = get(mid);
            int compareResult = comparator.compare(midElement, target);

            if (compareResult == 0) {
                return mid;
            } else if (compareResult < 0) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

调用示例 #

如果要按姓名搜索，你可以创建一个只比较姓名的比较器，或者直接用lambda表达式：

// 搜索姓名为"张三"的学生
Student target = new Student(); // 这里可以只设置姓名，其他字段不用填
target.setFullName("张三");
int index = studentList.binarySearch(target, (s1, s2) -> s1.getFullName().compareTo(s2.getFullName()));

// 或者忽略大小写的搜索
int caseInsensitiveIndex = studentList.binarySearch(target, 
    (s1, s2) -> s1.getFullName().toLowerCase().compareTo(s2.getFullName().toLowerCase()));

关键注意点 #

• 一定要保证列表严格按照你使用的比较规则有序，否则二分搜索会返回错误结果。比如用方案一按姓名搜索，列表必须是按姓名升序排列的；如果是降序，需要调整比较后的边界逻辑。
• 代码中get(int index)是假设你的ADT已经实现了通过索引获取元素的方法，如果没有，需要先实现这个基础方法（毕竟SortedArrayList底层是数组，实现起来很简单）。
• 关于返回值：如果没找到元素，你可以返回-1，也可以返回-(low + 1)来表示如果插入该元素应该在的位置，这和Java内置的Arrays.binarySearch行为一致，方便后续插入操作。

内容的提问来源于stack exchange，提问作者Cash-