Xətti və binar axtarış üçün tapşırıq nümunələri

3.1 Xətti axtarışdan istifadə edərək massivdə element tapmaq üzrə məsələ

Məsələ: Array verilmişdir. Xətti axtarışdan istifadə edərək verilmiş ədədin indeksini tapmaq lazımdır. Əgər ədəd tapılmadısa, -1 qaytarılmalıdır.

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 = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Element {target} indekste tapıldı: {result}")  # Çıxış: Element 7 indekste tapıldı: 2

# Array-də olmayan element üçün istifadə nümunəsi:
target = 5
result = linear_search(arr, target)
print(f"Element {target} indekste tapıldı: {result}")  # Çıxış: Element 5 indekste tapıldı: -1

İzah:

• linear_search funksiyası arr massivinin hər bir elementinə nəzər salır və onu target ilə müqayisə edir.
• Əgər element tapılırsa, həmin elementin indeksi qaytarılır.
• Əgər bütün elementlər yoxlanırsa və tələb olunan dəyər tapılmırsa, funksiya -1 qaytarır.

Merhələli icra:

1. Massiv [4, 2, 7, 1, 9, 3] və axtarılan dəyər 7.
2. Axtarışın başlanması: birinci element (4) ilə 7 müqayisə olunur — uyğun deyil.
3. Növbəti elementə keçid (2) — uyğun deyil.
4. Növbəti elementə keçid (7) — uyğun gəlir.
5. İndeks 2 qaytarılır.

3.2 İkilik axtarışdan istifadə edərək sıraya düzülmüş massivdə element tapmaq üçün tapşırıq

Tapşırıq: Sıraya düzülmüş ədədlərdən ibarət massiv verilib. İkilik axtarışdan istifadə edərək verilmiş ədədin indeksini tapmaq lazımdır. Əgər ədəd tapılmazsa, -1 qaytarılacaq.

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

# İstifadə nümunəsi:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Element {target} indeksdə tapıldı {result}")  # Çıxış: Element 7 indeksdə tapıldı 3

# Massivdə olmayan element üçün istifadə nümunəsi:
target = 6
result = binary_search(sorted_array, target)
print(f"Element {target} indeksdə tapıldı {result}")  # Çıxış: Element 6 indeksdə tapıldı -1

İzah:

• binary_search funksiyası massivdəki (arr) axtarışı izləmək üçün iki göstəricidən (left və right) istifadə edir.
• Hər iterasiyada massivdə orta element tapılıb target ilə müqayisə edilir.
• Əgər orta element target-ə bərabərdirsə, onun indeksi qaytarılır.
• Əgər target orta elementdən kiçikdirsə, axtarış massivdən sol tərəfdə davam edir.
• Əgər target orta elementdən böyükdürsə, axtarış massivdən sağ tərəfdə davam edir.
• Əgər sərhədlər kəsişirsə və element tapılmazsa, -1 qaytarılır.

Addım-addım icra:

1. Massiv [1, 3, 5, 7, 9, 11, 13] və axtarılan dəyər 7.
2. Axtarışın ilkin sərhədləri: left = 0, right = 6.
3. Orta elementin tapılması: mid = (0 + 6) // 2 = 3.
4. Orta elementin (7) target (7) ilə müqayisəsi — eynidir.
5. İndeks 3 qaytarılır.

3.3 Müxtəlif məsələlər üçün uyğun axtarış alqoritminin seçimi və müqayisəsi

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

Uyğun alqoritmin seçimi

Xətti axtarış:

• Data sortlaşdırılmayıbsa istifadə olunur.
• Kiçik massivlər və ya siyahılar üçün uyğundur.
• Elementlərin sayı az olduqda və vaxt kritiklik təşkil etmədikdə tətbiq edilir.

Binary axtarış:

• Data sortlaşdırılmış olduqda tətbiq edilir.
• Sürət vacib olduqda böyük massivlər üçün idealdır.
• Eyni data dəstində tez-tez axtarış tələb olunursa, effektivdir (öncədən datanı sortlaşdırmaq olar).

3.4 Materialın möhkəmləndirilməsi üçün praktik tapşırıqlar

Tapşırıq 1: Xətti axtarış

Rəqəmlərdən ibarət array verilib. Xətti axtarışdan istifadə edərək verilmiş rəqəmi tapmaq üçün funksiya yazın. Funksiya tapılmış elementin indeksini qaytarmalıdır və ya əgər element tapılmayıbsa -1 qaytarmalıdır.

Nümunə:

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

# Nümunə istifadə:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Element {target} indeksdə {result} tapıldı")  # Çıxış: Element 7 indeksdə 2 tapıldı

# Əlavə testlər:
assert linear_search(arr, 9) == 4
assert linear_search(arr, 5) == -1

Tapşırıq 2: Binary search

Sıralanmış rəqəmlərdən ibarət array verilib. Binary search-dan istifadə edərək verilmiş rəqəmi tapmaq üçün funksiya yazın. Funksiya tapılmış elementin indeksini qaytarmalı və ya əgər element tapılmayıbsa -1 qaytarmalıdı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

# Nümunə istifadə:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Element {target} indeksdə {result} tapıldı")  # Çıxış: Element 7 indeksdə 3 tapıldı

# Əlavə testlər:
assert binary_search(sorted_array, 1) == 0
assert binary_search(sorted_array, 13) == 6
assert binary_search(sorted_array, 6) == -1

Tapşırıq 3: Xətti və binary search-in müqayisəsi

Rəqəmlərdən ibarət array verilib. Verilmiş rəqəmi tapmaq üçün iki funksiya yazın: biri xətti axtarışdan istifadə etsin, digəri isə binary search-dan istifadə etsin. Böyük array-lərdə hər iki funksiyanın performansını müqayisə edin.

Nümunə:

import time
import random

# Xətti axtarış
def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# Binary search
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

# Böyük array yaradılması
large_array = [random.randint(0, 1000000) for _ in range(1000000)]
sorted_large_array = sorted(large_array)
target = random.choice(large_array)

# Performans müqayisəsi
start_time = time.time()
linear_search(large_array, target)
print(f"Xətti axtarış müddəti: {time.time() - start_time:.6f} saniyə")

start_time = time.time()
binary_search(sorted_large_array, target)
print(f"Binary search müddəti: {time.time() - start_time:.6f} saniyə")