Ví dụ bài toán cho tìm kiếm tuyến tính và nhị phân

3.1 Bài toán tìm phần tử trong mảng sử dụng tìm kiếm tuyến tính

Bài toán: Cho một mảng số. Cần tìm chỉ số của số đã cho bằng cách sử dụng tìm kiếm tuyến tính. Nếu số không được tìm thấy, trả về -1.

Ví dụ:

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

# Ví dụ sử dụng:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Phần tử {target} được tìm thấy ở chỉ số {result}")  # Kết quả: Phần tử 7 được tìm thấy ở chỉ số 2

# Ví dụ sử dụng cho phần tử không có trong mảng:
target = 5
result = linear_search(arr, target)
print(f"Phần tử {target} được tìm thấy ở chỉ số {result}")  # Kết quả: Phần tử 5 được tìm thấy ở chỉ số -1

Giải thích:

• Hàm linear_search duyệt qua từng phần tử trong mảng arr và so sánh nó với target.
• Nếu phần tử được tìm thấy, trả về chỉ số của nó.
• Nếu tất cả phần tử đã được kiểm tra và giá trị cần tìm không được tìm thấy, hàm trả về -1.

Thực hiện từng bước:

1. Mảng [4, 2, 7, 1, 9, 3] và giá trị cần tìm 7.
2. Bắt đầu tìm kiếm: so sánh phần tử đầu tiên (4) với 7 — không khớp.
3. Chuyển sang phần tử tiếp theo (2) — không khớp.
4. Chuyển sang phần tử tiếp theo (7) — khớp.
5. Trả về chỉ số 2.

3.2 Bài toán tìm phần tử trong mảng đã sắp xếp sử dụng tìm kiếm nhị phân

Bài toán: Cho một mảng số đã sắp xếp. Cần tìm chỉ số của số đã cho bằng cách sử dụng tìm kiếm nhị phân. Nếu số không được tìm thấy, trả về -1.

Ví dụ:

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

# Ví dụ sử dụng:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Phần tử {target} được tìm thấy ở chỉ số {result}")  # Kết quả: Phần tử 7 được tìm thấy ở chỉ số 3

# Ví dụ sử dụng cho phần tử không có trong mảng:
target = 6
result = binary_search(sorted_array, target)
print(f"Phần tử {target} được tìm thấy ở chỉ số {result}")  # Kết quả: Phần tử 6 được tìm thấy ở chỉ số -1

Giải thích:

• Hàm binary_search sử dụng hai chỉ báo (left và right), để theo dõi giới hạn tìm kiếm trong mảng arr.
• Ở mỗi vòng lặp, tìm phần tử giữa của mảng và so sánh với target.
• Nếu phần tử giữa bằng target, trả về chỉ số của nó.
• Nếu target nhỏ hơn phần tử giữa, tìm kiếm tiếp ở nửa trái của mảng.
• Nếu target lớn hơn phần tử giữa, tìm kiếm tiếp ở nửa phải của mảng.
• Nếu giới hạn giao nhau và phần tử không được tìm thấy, trả về -1.

Thực hiện từng bước:

1. Mảng đã sắp xếp [1, 3, 5, 7, 9, 11, 13] và giá trị cần tìm 7.
2. Giới hạn tìm kiếm ban đầu: left = 0, right = 6.
3. Tìm phần tử giữa: mid = (0 + 6) // 2 = 3.
4. So sánh phần tử giữa (7) với target (7) — khớp.
5. Trả về chỉ số 3.

3.3 So sánh và lựa chọn thuật toán tìm kiếm thích hợp cho các bài toán khác nhau

So sánh tìm kiếm tuyến tính và nhị phân:

Lựa chọn thuật toán phù hợp

Tìm kiếm tuyến tính:

• Được sử dụng khi dữ liệu chưa được sắp xếp.
• Phù hợp cho mảng hoặc danh sách nhỏ.
• Áp dụng khi số lượng phần tử không lớn và thời gian thực thi không quan trọng.

Tìm kiếm nhị phân:

• Áp dụng khi dữ liệu đã được sắp xếp.
• Lý tưởng cho mảng lớn, nơi tốc độ tìm kiếm quan trọng.
• Hiệu quả nếu yêu cầu tìm kiếm thường xuyên trên cùng một tập dữ liệu (có thể sắp xếp dữ liệu trước).

3.4 Bài tập thực hành để củng cố kiến thức

Bài tập 1: Tìm kiếm tuyến tính

Cho một mảng số. Viết hàm tìm kiếm số đã cho bằng cách sử dụng tìm kiếm tuyến tính. Hàm phải trả về chỉ số của phần tử đã tìm thấy hoặc -1 nếu không tìm thấy phần tử.

Ví dụ:

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

# Ví dụ sử dụng:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Phần tử {target} được tìm thấy ở chỉ số {result}")  # Kết quả: Phần tử 7 được tìm thấy ở chỉ số 2

# Các bài kiểm tra bổ sung:
assert linear_search(arr, 9) == 4
assert linear_search(arr, 5) == -1

Bài tập 2: Tìm kiếm nhị phân

Cho một mảng số đã sắp xếp. Viết hàm tìm kiếm số đã cho bằng cách sử dụng tìm kiếm nhị phân. Hàm phải trả về chỉ số của phần tử đã tìm thấy hoặc -1 nếu không tìm thấy phần tử.

Ví dụ:

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

# Ví dụ sử dụng:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Phần tử {target} được tìm thấy ở chỉ số {result}")  # Kết quả: Phần tử 7 được tìm thấy ở chỉ số 3

# Các bài kiểm tra bổ sung:
assert binary_search(sorted_array, 1) == 0
assert binary_search(sorted_array, 13) == 6
assert binary_search(sorted_array, 6) == -1

Bài tập 3: So sánh tìm kiếm tuyến tính và nhị phân

Cho một mảng số. Viết hai hàm để tìm kiếm số đã cho: một sử dụng tìm kiếm tuyến tính, một sử dụng tìm kiếm nhị phân. So sánh hiệu suất của cả hai hàm trên các mảng lớn.

Ví dụ:

import time
import random

# Tìm kiếm tuyến tính
def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# Tìm kiếm nhị phân
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

# Tạo mảng lớn
large_array = [random.randint(0, 1000000) for _ in range(1000000)]
sorted_large_array = sorted(large_array)
target = random.choice(large_array)

# So sánh hiệu suất
start_time = time.time()
linear_search(large_array, target)
print(f"Tìm kiếm tuyến tính mất: {time.time() - start_time:.6f} giây")

start_time = time.time()
binary_search(sorted_large_array, target)
print(f"Tìm kiếm nhị phân mất: {time.time() - start_time:.6f} giây")