跳转至

线性搜索

字数 389 个   代码 61 行   图片 1 张   阅读时间 2 分钟   访问量

一句话解释

从头到尾逐个比较数据结构中的每个元素,直到找到目标值或遍历完所有元素​​。

一、算法图解

1.1 Manim 动画演示

linear-search

Manim 动画演示源代码

1.2 Mermaid 流程图示意

graph TD

二、算法性质

2.1 时间复杂度

时间复杂度为 \(O(n)\)

2.2 空间复杂度

空间复杂度为 \(O(1)\)

2.3 其它性质

三、算法实现

3.1 多语言代码

下面提供了多种语言的版本,仅供参考。部分编程语言下方提供了可视化代码,但加载可能稍慢,请耐心等待。

1
2
3
4
5
def linear_search(arr: list[int], target: int) -> int:
    for i, v in enumerate(arr):
        if v == target:
            return i
    return -1
可视化代码 🔍全屏查看

1
2
3
4
5
6
7
8
int linearSearch(const std::vector<int> &arr, int target) {
    for (const auto &[i, v] : arr | std::views::enumerate) {
        if (v == target) {
            return i;
        }
    }
    return -1;
}
可视化代码 🔍全屏查看

1
2
3
4
5
6
7
8
int linearSearch(ArrayList<Integer> arr, Integer target) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr.get(i).equals(target)) {
            return i;
        }
    }
    return -1;
}
可视化代码 🔍全屏查看

1
2
3
4
5
6
7
8
function linearSearch(arr, target) {
    for (const [i, v] of arr.entries()) {
        if (v === target) {
            return i;
        }
    }
    return -1;
}
可视化代码 🔍全屏查看

1
2
3
4
5
6
7
8
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}
可视化代码 🔍全屏查看

1
2
3
4
5
6
7
8
int LinearSearch(List<int> arr, int target) {
    for (int i = 0; i < arr.Count; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

非常抱歉!pythontutor 暂时还不支持 C# 的可视化!

1
2
3
4
5
6
7
8
func linearSearch(arr []int, target int) int {
    for i, v := range arr {
        if v == target {
            return i
        }
    }
    return -1
}

非常抱歉!pythontutor 暂时还不支持 Go 的可视化!

1
2
3
4
5
6
7
8
fn linear_search(arr: &Vec<i32>, target: i32) -> i32 {
    for (i, &v) in arr.iter().enumerate() {
        if v == target {
            return i as i32;
        }
    }
    return -1;
}

非常抱歉!pythontutor 暂时还不支持 Rust 的可视化!

3.2 自我测试

下面是一个 Python 交互式环境,你可以在其中编写自己的代码进行一些测试。初次启动需要较长时间,请耐心等待!

交互式编程 🚀启动环境 ⚡运行

%reset -f

def linear_search(arr: list[int], target: int) -> int:
    pass

if __name__ == "__main__":
    arr: list[int] = [7, 0, 6, 1, 5, 2, 4, 3]
    print(linear_search(arr, 5))