Xətti Axtarış

1.1 Xətti axtarışın tərifi

Xətti axtarış (başqa adı ilə ardıcıl axtarış) — siyahıda və ya massivin içində elementin tapılması üçün bir alqoritmdir ki, hər bir elementi ardıcıl olaraq yoxlayır, uyğunluq tapana qədər və ya bütün elementləri yoxlayana qədər davam edir. Bu, ən sadə axtarış alqoritmidir və məlumatların əvvəlcədən çeşidlənməsini tələb etmir.

Əsas prinsiplər:

• Ardıcıl yoxlama: Alqoritm massiv və ya siyahının hər bir elementindən keçərək, bu elementi axtarılan dəyər ilə müqayisə edir.
• Axtarışın dayandırılması: Axtarış, axtarılan dəyərə uyğunluq tapan zaman və ya bütün elementlər yoxlandıqda dayanır.
• Çeşidləməyə ehtiyac yoxdur: Xətti axtarış çeşidlənməmiş məlumatlara tətbiq oluna bilər.
• Tətbiq sahəsi: Xətti axtarış iterasiyanı dəstəkləyən istənilən məlumat strukturlarına, o cümlədən siyahılara və massivlərə tətbiq edilə bilər.

Xətti axtarışın vaxt mürəkkəbliyi O(n)-dir, burada n — massivdə və ya siyahıda olan elementlərin sayıdır. Ən pis halda alqoritm, axtarılan dəyəri tapmaq və ya onun olmadığını müəyyən etmək üçün bütün n elementləri yoxlamalıdır.

Vaxt mürəkkəbliyinin təhlili:

• Ən yaxşı hal (Best case): Element ilk yerdə tapılır, O(1).
• Orta hal (Average case): Element haradasa ortada tapılır, O(n/2), bu da O(n)-yə bərabərdir.
• Ən pis hal (Worst case): Element ən son yerdə tapılır və ya tapılmır, O(n).

1.2 Xətti axtarışın addım-addım reallaşdırılması

Xətti axtarışın addımları:

• İlkin qeyd: Axtarış üçün başlanğıc indeksi təyin edin (adətən sıfır indeksi).
• Ardıcıl yoxlama: Siyahı və ya massivdə hər elementi axtarılan dəyərə uyğunluğa yoxlayın.
• Bitmə şərti: Əgər element tapılarsa, onun indeksini geri qaytarın. Əgər bütün elementlər yoxlanılıb və axtarılan dəyər tapılmırsa, xüsusi bir dəyər qaytarılır (adətən -1 və ya None).

Python ilə xətti axtarış reallaşdırılması:

def linear_search(arr, target):
    # Massivin hər bir elementi üzərində keçirik
    for index, element in enumerate(arr):
        # Əgər cari element axtarılan dəyərə bərabərdirsə, onun indeksini geri qaytarırıq
        if element == target:
            return index
    # Əgər element tapılmırsa, -1 qaytarırıq
    return -1

Reallaşdırmanın addım-addım izahı:

• Dövrün ilkin şərti: for dövrü enumerate funksiyası ilə birgə istifadə olunur, hansı ki, hər iterasiyada massivdən indeks və elementi qaytarır.
• Müqayisə: Hər iterasiyada cari element axtarılan dəyərlə (target) müqayisə olunur.
• İndeksin geri qaytarılması: Əgər cari element axtarılan dəyərə bərabərdirsə, həmin elementin indeksi geri qaytarılır.
• -1 geri qaytarılması: Əgər dövr başa çatır və axtarılan element tapılmırsa, -1 qaytarılır.

# İstifadə nümunəsi:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Element {target} indeksi {result}-də tapıldı")  # Çıxış: Element 7 indeksi 2-də tapıldı

# Massivdə mövcud olmayan element üçün nümunə:
target = 5
result = linear_search(arr, target)
print(f"Element {target} indeksi {result}-də tapıldı")  # Çıxış: Element 5 indeksi -1-də tapıldı

1.3 Xətti axtarışla həll olunan məsələlərə nümunələr

Xətti axtarış çoxlu məlumat kolleksiyalarında elementlərin tapılması ilə bağlı bir çox məsələləri həll etmək üçün istifadə olunur. Budur belə məsələlərə bir neçə nümunə:

Məsələ 1: Massivdə elementi tapmaq

Massivdə verilmiş rəqəmi tapmaq lazımdır.

Nümunə:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

arr = [10, 23, 45, 70, 11, 15]
target = 70
index = linear_search(arr, target)
print(f"Element {target} indeksdə tapıldı: {index}")  # Çıxış: Element 70 indeksdə tapıldı: 3

Məsələ 2: Siyahıda elementin mövcudluğunu yoxlamaq

Verilmiş dəyərin sətirlər siyahısında mövcud olub-olmadığını yoxlamaq lazımdır.

Nümunə:

def linear_search(arr, target):
    for element in arr:
        if element == target:
            return True
    return False

words = ["apple", "banana", "cherry", "date"]
target = "cherry"
found = linear_search(words, target)
print(f"Element {target} {'tapıldı' if found else 'tapılmadı'}")  # Çıxış: Element cherry tapıldı

Məsələ 3: Minimal və ya maksimal elementi tapmaq

Verilmiş siyahıda minimal və ya maksimal dəyəri tapmaq lazımdır.

Nümunə:

def find_min(arr):
    if not arr:
        return None
    min_val = arr[0]
    for element in arr:
        if element < min_val:
            min_val = element
    return min_val

arr = [34, 17, 23, 2, 45, 13]
min_value = find_min(arr)
print(f"Minimal dəyər: {min_value}")  # Çıxış: Minimal dəyər: 2

Məsələ 4: İlk qarşılaşmanı tapmaq

Siyahıda verilmiş elementin ilk qarşılaşmasını tapmaq lazımdır.

Nümunə:

def find_first_occurrence(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

arr = [4, 2, 7, 1, 9, 3, 2]
target = 2
index = find_first_occurrence(arr, target)
print(f"İlk qarşılaşma {target} indeksdədir: {index}")  # Çıxış: İlk qarşılaşma 2 indeksdədir: 1

Məsələ 5: Qarşılaşma sayını tapmaq

Siyahıda verilmiş elementin neçə dəfə qarşılaşdığını saymaq lazımdır.

Nümunə:

def count_occurrences(arr, target):
    count = 0
    for element in arr:
        if element == target:
            count += 1
    return count

arr = [4, 2, 7, 2, 9, 3, 2]
target = 2
count = count_occurrences(arr, target)
print(f"Element {target} {count} dəfə rast gəlinir")  # Çıxış: Element 2 3 dəfə rast gəlinir