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; // 遍历完数组仍未找到
    }

    // ... 二分搜索方法将在此处添加
}

public class Search {

    // ... 线性搜索方法

    /**
     * 在给定已排序数组中执行二分搜索。
     *
     * @param arr          待搜索的已排序整数数组。
     * @param low          当前搜索范围的起始索引。
     * @param high         当前搜索范围的结束索引。
     * @param numberToFind 目标整数。
     * @return 如果找到目标元素，返回其在数组中的索引；否则返回 -1。
     */
    public int binarySearch(int[] arr, int low, int high, int numberToFind) {
        if (high >= low) {
            // 计算中间索引，避免整数溢出风险
            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() {
        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(); // 创建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("--- 二分搜索测试 ---");
        // 示例1: 对未排序数组进行二分搜索 (将产生错误结果)
        int[] unsortedArray = {2, 3, 5, 4, 30};
        int targetBinaryUnsorted = 4;
        System.out.println("注意：对未排序数组进行二分搜索通常会失败或给出错误结果。");
        tester.testBinarySearch(unsortedArray, targetBinaryUnsorted);
        System.out.println();

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