Java中线性搜索与二分搜索的实现与测试指南

public class Search {

    /**
     * 线性搜索方法，用于在数组中查找指定元素。
     *
     * @param arr          要搜索的整数数组。
     * @param numberToFind 要查找的目标整数。
     * @return 如果找到目标元素，返回其在数组中的索引；否则返回 -1。
     */
    public int linearSearch(int arr[], int numberToFind) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if (arr[i] == numberToFind) {
                return i; // 找到元素，返回其索引
            }
        }
        return -1; // 未找到元素
    }

    /**
     * 二分搜索方法，用于在已排序的数组中查找指定元素。
     * 注意：此方法要求输入的数组必须是升序排序的。
     *
     * @param arr          要搜索的已排序整数数组。
     * @param l            搜索范围的左边界索引。
     * @param r            搜索范围的右边界索引。
     * @param numberToFind 要查找的目标整数。
     * @return 如果找到目标元素，返回其在数组中的索引；否则返回 -1。
     */
    public int binarySearch(int arr[], int l, int r, int numberToFind) {
        if (r >= l) {
            // 计算中间索引，避免 (l+r) 溢出，更稳健的写法是 l + (r - l) / 2
            int mid = l + (r - l) / 2; // 修正了原始代码中 mid 的计算错误

            if (arr[mid] == numberToFind) {
                return mid; // 找到元素
            }

            // 如果目标值小于中间元素，则在左半部分继续搜索
            if (arr[mid] > numberToFind) {
                return binarySearch(arr, l, mid - 1, numberToFind);
            }

            // 如果目标值大于中间元素，则在右半部分继续搜索
            return binarySearch(arr, mid + 1, r, numberToFind);
        }
        return -1; // 未找到元素
    }
}

public class MainTester {
    private Search search; // 声明一个 Search 类的实例

    /**
     * MainTester 类的构造器，用于初始化 Search 对象。
     */
    public MainTester() {
        this.search = new Search();
    }

    /**
     * 测试线性搜索方法。
     *
     * @param numberArray  要搜索的数组。
     * @param numberToFind 要查找的数字。
     */
    public void testLinearSearch(int[] numberArray, int numberToFind) {
        int result = search.linearSearch(numberArray, numberToFind);
        printResult("线性搜索", numberToFind, result);
    }

    /**
     * 测试二分搜索方法。
     * 注意：此方法要求输入的数组必须是升序排序的，否则结果可能不准确。
     *
     * @param arr          要搜索的数组。
     * @param numberToFind 要查找的数字。
     */
    public void testBinarySearch(int[] arr, int numberToFind) {
        // 二分搜索的初始调用通常是从索引 0 到 arr.length - 1
        int result = search.binarySearch(arr, 0, arr.length - 1, numberToFind);
        printResult("二分搜索", numberToFind, result);
    }

    /**
     * 辅助方法：统一打印搜索结果。
     *
     * @param searchType   搜索类型（如“线性搜索”、“二分搜索”）。
     * @param searchNumber 要查找的数字。
     * @param arrayIndex   查找结果的索引（-1 表示未找到）。
     */
    private void printResult(String searchType, int searchNumber, int arrayIndex) {
        if (arrayIndex == -1) {
            System.out.println(searchType + ": 元素 " + searchNumber + " 未在数组中找到。");
        } else {
            System.out.println(searchType + ": 元素 " + searchNumber + " 在数组中的索引为 " + arrayIndex + "。");
        }
    }

    public static void main(String args[]) {
        MainTester tester = new MainTester(); // 创建 MainTester 实例

        System.out.println("--- 线性搜索测试 ---");
        int numberToFindLinear = 10;
        int[] arrLinear = {2, 3, 4, 10, 30};
        tester.testLinearSearch(arrLinear, numberToFindLinear);
        tester.testLinearSearch(arrLinear, 50); // 测试未找到的情况

        System.out.println("\n--- 二分搜索测试 ---");
        // 尝试在未排序数组上进行二分搜索：结果可能不准确或错误
        int numberToFindBinaryUnsorted = 4;
        int[] unsortedArray = {2, 3, 5, 4, 30}; // 注意：此数组未排序
        System.out.println("在未排序数组上执行二分搜索 (预期结果可能不准确):");
        tester.testBinarySearch(unsortedArray, numberToFindBinaryUnsorted);

        // 尝试在已排序数组上进行二分搜索：正确的工作方式
        int numberToFindBinarySorted = 4;
        int sortedArray[] = {2, 3, 4, 5, 30}; // 注意：此数组已排序
        System.out.println("\n在已排序数组上执行二分搜索:");
        tester.testBinarySearch(sortedArray, numberToFindBinarySorted);
        tester.testBinarySearch(sortedArray, 30); // 测试边界值
        tester.testBinarySearch(sortedArray, 1); // 测试未找到的最小值
    }
}