Xətti axtarış (linear search) ən sadə axtarış alqoritmidir: elementlərə birbaşa soldan sağa baxırıq. O, çeşidləmə tələb etmir və istənilən ardıcıllıq üzərində işləyir. Çeşidlənmiş məlumat üçün daha sürətli üsul: ikili axtarış.

![[4, 9, 2, 7, 5] içində 7 axtarışı](img/lessons/algorithms/linear-search-trace.svg)

Alqoritm və invariant

Hər addımda a[i]-ni x ilə müqayisə edirik. İnvariant: i-ci addımdan əvvəl x a[0..i-1] hissəsində yoxdur. Bərabərlik tapılanda i birinci uyğunluqdur; dövr bitəndə invariant x-in bütün siyahıda olmadığını deyir, ona görə -1 qaytarılır. Düzgünlük haqqında: invariantlar.

python
def linear_search(a, x):
    for i, v in enumerate(a):
        if v == x:
            return i               # first occurrence
    return -1                      # not found

data = [4, 9, 2, 7, 5]
print(linear_search(data, 7))
print(linear_search(data, 8))
print(linear_search([], 1))
text
3
-1
-1

Ən yaxşı, ən pis və orta hal