本文详细介绍了如何在Java中实现线性搜索和二分搜索算法，并提供了规范的测试方法。内容涵盖了算法的核心逻辑、代码实现细节、Java编程最佳实践，如命名约定、代码模块化以及面向对象设计原则，旨在帮助读者构建高效且易于维护的搜索功能。
在软件开发中，搜索算法是基础且常用的工具，用于在数据集合中查找特定元素。本文将深入探讨两种最常见的搜索算法：线性搜索（Linear Search）和二分搜索（Binary Search），并提供完整的Java实现及测试方法。
线性搜索是最简单直观的搜索算法。它通过遍历数组中的每一个元素，将它们与目标值（键）进行比较。如果找到匹配项，则返回其索引；如果遍历完整个数组仍未找到，则表示元素不存在。
二分搜索是一种高效的搜索算法，但它有一个关键前提：数据集合必须是已排序的。该算法通过不断将搜索区间减半来逼近目标值。它首先检查数组的中间元素，如果中间元素是目标值，则搜索成功；如果目标值小于中间元素，则在左半部分继续搜索；如果目标值大于中间元素，则在右半部分继续搜索。这个过程递归进行，直到找到目标值或搜索区间为空。
我们将创建一个名为 Search 的类来封装线性搜索和二分搜索的逻辑。
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; // 未找到元素
}
}代码要点说明：
为了验证 Search 类中方法的正确性，我们将创建一个 MainTester 类。这个类将负责创建 Search 类的实例，并调用其方法进行测试。
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); // 查找不存在的元素
}
}代码要点说明：
