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 low          当前搜索区间的起始索引。
     * @param high         当前搜索区间的结束索引。
     * @param numberToFind 要查找的整数。
     * @return 如果找到元素，返回其在数组中的索引；否则返回 -1。
     */
    public int binarySearch(int[] arr, int low, int high, int numberToFind) {
        if (high >= low) {
            // 计算中间索引，避免 (low + high) 溢出
            int mid = low + (high - low) / 2; 

            // 如果中间元素是目标值
            if (arr[mid] == numberToFind) {
                return mid;
            }

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

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

public class MainTester {
    private Search search; // Search类的实例

    /**
     * 构造函数，初始化 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) {
        // 二分搜索的初始调用范围是整个数组
        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();

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

        // --- 二分搜索测试 ---
        System.out.println("--- 二分搜索测试 ---");
        // 1. 使用未排序数组进行二分搜索：将不会得到正确结果
        int[] unsortedArray = {2, 3, 5, 4, 30};
        int numberToFindBinaryUnsorted = 4;
        System.out.println("使用未排序数组进行二分搜索 (预期结果可能不准确):");
        tester.testBinarySearch(unsortedArray, numberToFindBinaryUnsorted); // 预期结果可能不准确

        System.out.println();

        // 2. 使用已排序数组进行二分搜索：正确用法
        int[] sortedArray = {2, 3, 4, 5, 30};
        int numberToFindBinarySorted = 4;
        System.out.println("使用已排序数组进行二分搜索 (预期结果正确):");
        tester.testBinarySearch(sortedArray, numberToFindBinarySorted); // 查找存在的元素
        tester.testBinarySearch(sortedArray, 10); // 查找不存在的元素
    }
}