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) {
            // 计算中间元素的索引
            // 修正：原始代码中 mid = l + (r - 1) / 2 在某些情况下可能导致整数溢出或计算错误
            // 更安全的计算方式是 mid = l + (r - l) / 2 或 mid = (l + r) / 2
            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 类的实例

    /**
     * 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 实例

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

        // 2. 二分搜索测试 (未排序数组 - 会导致错误结果)
        System.out.println("--- 二分搜索测试 (未排序数组 - 结果可能不正确) ---");
        int[] unsortedArray = {2, 3, 5, 4, 30}; // 注意：此数组未排序
        tester.testBinarySearch(unsortedArray, 4); // 查找存在的元素
        tester.testBinarySearch(unsortedArray, 1); // 查找不存在的元素
        System.out.println();

        // 3. 二分搜索测试 (已排序数组 - 正确结果)
        System.out.println("--- 二分搜索测试 (已排序数组 - 正确结果) ---");
        int[] sortedArray = {2, 3, 4, 5, 30}; // 注意：此数组已排序
        tester.testBinarySearch(sortedArray, 4);  // 查找存在的元素
        tester.testBinarySearch(sortedArray, 30); // 查找存在的元素
        tester.testBinarySearch(sortedArray, 1);  // 查找不存在的元素
        System.out.println();
    }
}