Axtarış üzrə alqoritmik məsələlər

9.1 Xətti və binary search ilə həll olunan məsələlərin nümunələri

Xətti axtarış

Massivdə elementin axtarışı məsələsi: Rəqəmlərdən ibarət massiv və bir hədəf dəyəri verilib. Hədəf dəyərini massivdə tapıb indeksini qaytarmaq tələb olunur.

Həll: Massivin hər bir elementini yoxlamaq üçün xətti axtarışdan istifadə edirik.

Reallaşdırma nümunəsi:

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

# İstifadə nümunəsi:
arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target))  # Çıxış: 2

Binary search

Sortlanmış massivdə elementin axtarışı məsələsi: Sortlanmış rəqəmlər massivi və bir hədəf dəyəri verilib. Hədəf dəyərini massivdə tapıb indeksini qaytarmaq tələb olunur.

Həll: Massivi yarıya bölmək və hədəf dəyərini tapmaq üçün binary search istifadə edirik.

Reallaşdırma nümunəsi:

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

# İstifadə nümunəsi:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target))  # Çıxış: 3

9.2 Axtarışı optimallaşdırmaq üçün hash-cədvəllərdən istifadə məsələləri

1. Massivdə təkrarlanan elementlərin axtarışı

Məsələ: Verilmiş ədədlər massivində bütün təkrarlanan elementləri tapıb qaytarmaq lazımdır.

Həll: Artıq qarşılaşılmış ədədləri izləmək üçün hash-cədvəldən istifadə edirik. Əgər ədəd təkrar yerləşir, onu təkrarlanan elementlərin siyahısına əlavə edirik.

Nümunə implementasiya:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# İstifadə nümunəsi
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # Çıxış: [2, 4]

2. Müəyyən cəmlə cütlüklərin tapılması

Məsələ: Verilmiş ədədlər massivi və müəyyən cəml dəyəri var. Cəmləri müəyyən edərəq dəyərə bərabər olan bütün ədədlər cütlərini tapmaq lazımdır.

Həll: Hash-cədvəldən ədədləri saxlamaq və mövcud ədədin müəyyən bir cüt yaratdığını yoxlamaq üçün istifadə edirik, hansı ki, həmin cüt təyin edilmiş cəmi verir.

Nümunə implementasiya:

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []

    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)

    return pairs

# İstifadə nümunəsi
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Çıxış: [(1, 5), (7, -1), (1, 5)]

9.3 Müxtəlif axtarış metodlarının birləşdirilmiş istifadəsi

Çətin məsələlərdə tez-tez maksimum effektivliyə nail olmaq üçün bir neçə axtarış metodundan istifadə etmək lazımdır. Xətti axtarış, binary search və hash-table birləşdirilmiş istifadəsi məsələləri daha effektiv və çevik həll etməyə imkan verir.

Məsələn 1: Massivdə elementin axtarışı və başqa bir massivdə onun mövcudluğunun yoxlanması

İki massiv rəqəm verilib. Birinci massivdəki elementləri tapmaq lazımdır ki, onlar ikinci massivdə mövcuddur.

Həll:

• İkinci massiv elementlərini saxlamaq üçün hash-table istifadə edirik.
• Birinci massivdəki hər bir element üçün onun hash-table-də mövcudluğunu yoxlayırıq.

Reallaşdırma nümunəsi:

def find_common_elements(arr1, arr2):
    hash_table = set(arr2)  # İkinci massiv üçün hash-table
    common_elements = []

    for element in arr1:
        if element in hash_table:
            common_elements.append(element)

    return common_elements

# İstifadə nümunəsi:
arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
print(find_common_elements(arr1, arr2))  # Çıxış: [3, 4, 5]

Məsələn 2: Submassivin anagram array olub-olmadığını hash-table-dan istifadə ilə yoxlamaq

String massivi və pattern verilib. String massivində hər hansı bir substring-in pattern-in anagramı olub-olmadığını yoxlamaq lazımdır.

Həll:

• Pattern-in simvol tezliyini hesablamaq üçün hash-table istifadə edirik.
• String massivini keçir və simvol tezliklərinə uyğunluğu yoxlamaq üçün "skidən pəncərə" istifadə edirik.

Reallaşdırma nümunəsi:

from collections import Counter

def is_anagram(s1, s2):
    return Counter(s1) == Counter(s2)

def find_anagram_substring(arr, pattern):
    pattern_length = len(pattern)
    pattern_count = Counter(pattern)
    
    for i in range(len(arr) - pattern_length + 1):
        substring = arr[i:i + pattern_length]
        if is_anagram(substring, pattern):
            return True
    return False

# İstifadə nümunəsi:
arr = "cbabadcbbabbcbabaabccbabc"
pattern = "abbc"
print(find_anagram_substring(arr, pattern))  # Çıxış: True

9.4 Mövzunu möhkəmləndirmək üçün praktiki tapşırıqlar

Tapşırıq 1: Nizamlanmamış massivdə elementin axtarışı

Verilmiş rəqəmlər massivi və bir məqsəd dəyəri. Məqsəd dəyərinin massivdəki indeksini tapmaq lazımdır. Lineer axtarışdan istifadə edin.

Nümunə:

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

# İstifadə nümunəsi:
arr = [10, 20, 30, 40, 50]
target = 30
print(linear_search(arr, target))  # Çıxış: 2

Tapşırıq 2: Massivdə təkrarlananların axtarışı

Verilmiş rəqəmlər massivi. Hash table-dan istifadə edərək massivdəki bütün təkrarlananları tapıb qaytarın.

Nümunə:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# İstifadə nümunəsi:
arr = [1, 3, 5, 3, 7, 9, 1]
print(find_duplicates(arr))  # Çıxış: [3, 1]