线性查找

查找与遍历

说明

逐项比较直到命中；无需排序，时间 O(n)。

分析

从头检查每个元素，第一次相等时返回下标。它不要求预处理或排序，数据很少或只查询一次时常是最简单的选择。

图解推演

补充数组 [4,2,7,2] 查找 2：先比较下标 0 的 4，再比较下标 1 的 2，立即返回 1。找到一次便返回决定了它输出最早匹配，而非全部匹配；不存在时必须扫描全部 n 项并返回约定的未找到值。

查看图表代码

适用前提与边界

若在同一大集合上反复查找，可以考虑排序后二分或建立哈希索引。

示例输入与调用

fmt.Println(LinearSearch([]int{4, 7, 9}, 7))

运行输出

1

完整 Go 示例

package main

import "fmt"

func LinearSearch(a []int, target int) int {
	for i, x := range a {
		if x == target {
			return i
		}
	}
	return -1
}

func main() {
	fmt.Println(LinearSearch([]int{4, 7, 9}, 7))
}