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; // 未找到目标
    }

    // ... 其他方法（如binarySearch）将在此处添加
}

public class Search {

    // ... linearSearch 方法

    /**
     * 实现二分搜索算法（递归版本）。
     * 注意：此方法要求输入的数组必须是已排序的。
     *
     * @param arr          要搜索的已排序整数数组。
     * @param l            当前搜索范围的左边界索引。
     * @param r            当前搜索范围的右边界索引。
     * @param numberToFind 要查找的目标数字。
     * @return 如果找到目标数字，返回其在数组中的索引；否则返回 -1。
     */
    public int binarySearch(int arr[], int l, int r, int numberToFind) {
        if (r >= l) {
            // 正确的中间索引计算方式，避免溢出（尽管在Java中不常见）
            int mid = l + (r - l) / 2; // 推荐写法，等同于(l + r) / 2 但更安全

            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类的实例

    /**
     * 构造函数，初始化Search类的实例。
     */
    public MainTester() {
        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 + "。");
        }
    }

    /**
     * 主方法，程序的入口点，用于执行所有测试。
     *
     * @param args 命令行参数。
     */
    public static void main(String args[]) {
        MainTester tester = new MainTester();

        System.out.println("--- 线性搜索测试 ---");
        int[] arrLinear = {2, 3, 4, 10, 30};
        int targetLinear = 10;
        tester.testLinearSearch(arrLinear, targetLinear); // 查找存在的元素
        tester.testLinearSearch(arrLinear, 5);          // 查找不存在的元素
        System.out.println();

        System.out.println("--- 二分搜索测试 (重要: 数组必须排序) ---");
        // 尝试对未排序的数组进行二分搜索：结果将不准确
        int targetBinaryUnsorted = 4;
        int[] unsortedArray = {2, 3, 5, 4, 30};
        System.out.println("对未排序数组进行二分搜索 (预期结果可能错误):");
        tester.testBinarySearch(unsortedArray, targetBinaryUnsorted); // 预期可能错误或找不到

        System.out.println("\n对已排序数组进行二分搜索:");
        // 对已排序的数组进行二分搜索：正常工作
        int targetBinarySorted = 4;
        int[] sortedArray = {2, 3, 4, 5, 30}; // 注意：4的索引是2
        tester.testBinarySearch(sortedArray, targetBinarySorted); // 查找存在的元素
        tester.testBinarySearch(sortedArray, 1);                 // 查找不存在的元素
    }
}