Xətti və binar axtarışın müqayisəsi

4.1 Xətti və ikili axtarışın vaxt mürəkkəbliyinin müqayisəsi

Gəlin xətti və ikili axtarışın vaxt mürəkkəbliyini müqayisə edək.

Xətti axtarış:

• Vaxt mürəkkəbliyi: O(n), burada n — massivdə və ya siyahıda elementlərin sayıdır.
• Ən yaxşı hal: O(1) — element ilk mövqedə tapılır.
• Orta hal: O(n/2) = O(n) — element orta yerdə haradasa tapılır.
• Ən pis hal: O(n) — element son yerdə tapılır və ya yoxdur.

İkili axtarış:

• Vaxt mürəkkəbliyi: O(log n), burada n — massivdə və ya siyahıda elementlərin sayıdır.
• Ən yaxşı hal: O(1) — element ilk addımda (orta element) tapılır.
• Orta hal: O(log n) — sıralanmış massivdə axtarış.
• Ən pis hal: O(log n) — element son addımda tapılır və ya yoxdur.

Vaxt mürəkkəbliyinin təhlilinə nümunə

Xətti axtarış:

• Massiv [1, 3, 5, 7, 9, 11, 13], axtarılan element 7.
• 7-ni tapana qədər hər elementi yoxlama.
• 7 üçüncü indeksdə tapıldı və 4 yoxlama lazım oldu ki, bu da O(n)-ə uyğundur.

İkili axtarış:

• Massiv [1, 3, 5, 7, 9, 11, 13], axtarılan element 7.
• Orta element (7) ilk addımda tapıldı.
• 1 yoxlama lazım oldu ki, bu da O(log n)-ə uyğundur.

4.2 Hər bir metodun üstünlükləri və çatışmazlıqları

Hər bir axtarış növünün üstünlükləri və çatışmazlıqlarını nəzərdən keçirək.

Xətti axtarış:

Üstünlüklər:

• Sadə realizasiya: Xətti axtarışı həyata keçirmək və başa düşmək çox asandır.
• Verilənlərə tələblər yoxdur: Xətti axtarış çeşidlənməmiş verilənlərdə tətbiq oluna bilər.
• Kiçik massivlər üçün uyğundur: Xətti axtarış kiçik ölçülü massivlər üçün effektivdir.

Çatışmazlıqlar:

• Böyük massivlər üçün aşağı effektivlik: Vaxt mürəkkəbliyi O(n) olduğuna görə, böyük massivlər üçün təsirsizdir.
• Uzun icra müddəti: Böyük massivlər üçün xətti axtarış çox vaxt apara bilər, xüsusilə axtarılan element massivdə sona yaxın yerləşirsə və ya yoxdur.

İkilik axtarış:

Üstünlüklər:

• Böyük massivlər üçün yüksək effektivlik: Vaxt mürəkkəbliyi O(log n) olduğuna görə, böyük massivlər üçün çox effektivdir.
• Tez icra: İkilik axtarış böyük çeşidli massivlərlə işləyərkən xətti axtarışdan xeyli tezdir.

Çatışmazlıqlar:

• Çeşidlənmiş verilənlər tələb edir: İkilik axtarış yalnız çeşidlənmiş massivlərlə işləyir ki, bu da əlavə vaxt tələb edə bilər.
• Reallaşdırma çətinliyi: İkilik axtarışın reallaşdırılması xətti axtarışla müqayisədə daha çətindir.

4.3 Hansı axtarışı nə zaman istifadə etməli

Gəlin baxaq, lineer axtarışı nə vaxt istifadə etməliyik, ikili axtarışı isə nə vaxt.

Lineer axtarış.

Lineer axtarışı istifadə edin, əgər:

• Massiv və ya siyahı sortlanmayıb.
• Massiv və ya siyahının ölçüsü kiçikdir.
• Sadəlik və əlavə sortlama mənbəyi tələb etməyən tez həll lazımdır.
• Elementin ilk yerləşməsini və ya bütün yerləşmələrini tapmaq lazımdır.
• Məlumatlar real vaxtda gəlir və onları öncədən sortlamaq mümkün deyil ya da məntiqsizdir.

İkili axtarış.

İkili axtarışı istifadə edin, əgər:

• Massiv və ya siyahı sortlanıb.
• Massiv və ya siyahının ölçüsü böyükdür.
• Eyni məlumat dəstəsində tez-tez element axtarışı aparılır (məlumatı bir dəfə öncədən sortlamaq olar).
• Axtarış sürətinin yüksək olması vacibdir.
• Məlumatların əvvəlcədən sortlanması üçün vaxt sərf etmək məqbuldur.

4.4 Xətti axtarış üçün misal tapşırıqlar

1. Sıralanmamış siyahıda axtarış

Verilmiş ədədi sıralanmamış ədədlər siyahısında tapıb indeksini müəyyən etmək lazımdır.

Misal:

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

arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target))  # Çıxış: 2

2. Massivdə ilk rast gəlməni tapmaq

Verilmiş elementi sətir massivində ilk dəfə rastlaşdığı yeri tapmaq lazımdır.

Misal:

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

words = ["alma", "banana", "gilas", "xurma", "banana"]
target = "banana"
print(linear_search(words, target))  # Çıxış: 1

3. Real vaxtda olan məlumatlarda axtarış

Real vaxtda gələn data axınında elementi tapmaq lazımdır.

Misal:

import random

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

stream = [random.randint(1, 100) for _ in range(100)]
target = 50
print(find_in_stream(stream, target))

4.5 Binary axtarış üçün nümunə məsələlər

1. Sıralanmış massivdə axtarış

Sıralanmış rəqəmlər massivində verilmiş bir ədədin indeksini tapmaq lazımdır.

Nümunə:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target))  # Çıxış: 3

2. Böyük məlumat dəstində tez-tez axtarış

Böyük sıralanmış rəqəmlər massivində elementləri tez-tez axtarmaq.

Nümunə:

import random

sorted_large_array = sorted([random.randint(1, 1000000) for _ in range(1000000)])
target = random.choice(sorted_large_array)
print(binary_search(sorted_large_array, target))

3. Sıralanmış məlumat bazasında element axtarışı

Açar sahəsi üzrə sıralanmış məlumat bazasında qeydi tapmaq.

Nümunə:

database = sorted([{"id": i, "value": f"record_{i}"} for i in range(100000)])
def binary_search_db(db, target_id):
    left, right = 0, len(db) - 1
    while left <= right:
        mid = (left + right) // 2
        if db[mid]["id"] == target_id:
            return db[mid]
        elif db[mid]["id"] < target_id:
            left = mid + 1
        else:
            right = mid - 1
    return None

target_id = 54321
print(binary_search_db(database, target_id))

1

Опрос

Axtarış alqoritmləri,  53 уровень,  3 лекция

недоступен

Axtarış alqoritmləri

Axtarış alqoritmləri

Открыть