如何统计线性搜索(Linear Search)执行过程中的总步骤数

核心修改逻辑 #

• 原有方法仅返回查找结果索引/不存在标识，我们新增步数统计逻辑：每执行1次数组元素匹配对比计为1步，遍历完所有元素未找到目标时，总步数等于数组长度
• 以下采用自定义结果类的方式实现，可读性更高，后期维护更方便

修复后完整代码 #

// 注意修正原文件名为 LinearSearch.java，原类名ArrayRotation已同步调整
public class LinearSearch {
    // 自定义结果类，同时存储查找结果和执行步数
    static class SearchResult {
        int index; // 目标元素索引，不存在时为-1
        int stepCount; // 查找总执行步数

        public SearchResult(int index, int stepCount) {
            this.index = index;
            this.stepCount = stepCount;
        }
    }

    public static SearchResult linearSearch(int []arr,int x){
        int n = arr.length;
        int step = 0;
        for (int i=0;i < n;i++){
            step++; // 每执行一次元素匹配就计数1步
            if (arr[i]== x)
                return new SearchResult(i, step);
        }
        return new SearchResult(-1, step);
    }

    public static void main(String[] args) {
        int arr[]={4,56,44,152,54,845};
        // 测试不存在的元素
        int x = 26;
        SearchResult result = linearSearch(arr,x);
        if (result.index == -1)
            System.out.println("查找元素不在数组中，总执行步数：" + result.stepCount);
        else
            System.out.println("查找元素位于索引" + result.index + "，总执行步数：" + result.stepCount);
        
        // 测试存在的元素
        x = 152;
        result = linearSearch(arr,x);
        if (result.index == -1)
            System.out.println("查找元素不在数组中，总执行步数：" + result.stepCount);
        else
            System.out.println("查找元素位于索引" + result.index + "，总执行步数：" + result.stepCount);
    }
}

输出示例 #

查找元素不在数组中，总执行步数：6
查找元素位于索引3，总执行步数：4

内容的提问来源于stack exchange，提问作者Mama