Bài toán tìm kiếm bằng thuật toán

9.1 Ví dụ về các bài toán giải quyết bằng tìm kiếm tuyến tính và nhị phân

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

Bài toán tìm phần tử trong mảng: Cho một mảng số và một giá trị mục tiêu. Cần tìm chỉ số của giá trị mục tiêu trong mảng.

Giải pháp: Sử dụng tìm kiếm tuyến tính để kiểm tra từng phần tử trong mảng.

Ví dụ triển khai:

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
print(linear_search(arr, target))  # Kết quả: 2

Tìm kiếm nhị phân

Bài toán tìm phần tử trong mảng đã sắp xếp: Cho một mảng số đã sắp xếp và một giá trị mục tiêu. Cần tìm chỉ số của giá trị mục tiêu trong mảng.

Giải pháp: Sử dụng tìm kiếm nhị phân để chia mảng thành các phần và tìm giá trị mục tiêu.

Ví dụ triển khai:

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
print(binary_search(sorted_array, target))  # Kết quả: 3

9.2 Bài toán sử dụng hash tables để tối ưu hóa tìm kiếm

1. Tìm kiếm các phần tử trùng lặp trong mảng

Bài toán: Cho một mảng số. Cần tìm và trả về tất cả các phần tử trùng lặp trong mảng.

Giải pháp: Sử dụng hash table để theo dõi các số đã gặp. Nếu một số xuất hiện lần thứ hai, thêm nó vào danh sách các phần tử trùng lặp.

Ví dụ triển khai:

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

# Ví dụ sử dụng:
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # Kết quả: [2, 4]

2. Tìm các cặp có tổng bằng một giá trị cho trước

Bài toán: Cho một mảng số và một giá trị tổng mục tiêu. Cần tìm tất cả các cặp số có tổng bằng giá trị mục tiêu.

Giải pháp: Sử dụng hash table để lưu trữ các số và kiểm tra xem chúng có tạo thành cặp với số hiện tại, có tổng bằng giá trị mục tiêu hay không.

Ví dụ triển khai:

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

# Ví dụ sử dụng
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Kết quả: [(1, 5), (7, -1), (1, 5)]

9.3 Sử dụng kết hợp các phương pháp tìm kiếm khác nhau

Trong những bài toán phức tạp, thường yêu cầu sử dụng nhiều phương pháp tìm kiếm để đạt hiệu quả tốt nhất. Sử dụng kết hợp tìm kiếm tuyến tính, tìm kiếm nhị phân và hash tables giúp giải quyết bài toán một cách hiệu quả và linh hoạt hơn.

Ví dụ 1: Tìm phần tử trong mảng và kiểm tra sự tồn tại của nó trong một mảng khác

Cho hai mảng số. Cần tìm các phần tử của mảng đầu tiên mà tồn tại trong mảng thứ hai.

Giải pháp:

• Sử dụng hash table để lưu trữ các phần tử của mảng thứ hai.
• Với mỗi phần tử của mảng đầu tiên, kiểm tra sự tồn tại của nó trong hash table.

Ví dụ triển khai:

def find_common_elements(arr1, arr2):
    hash_table = set(arr2)  # Hash table cho mảng thứ hai
    common_elements = []

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

    return common_elements

# Ví dụ sử dụng:
arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
print(find_common_elements(arr1, arr2))  # Kết quả: [3, 4, 5]

Ví dụ 2: Kiểm tra xem một dãy con có phải là một mảng của các anagram sử dụng hash table

Cho một mảng các chuỗi và một chuỗi mẫu. Cần kiểm tra xem có bất kỳ dãy con nào của mảng chuỗi là anagram của mẫu không.

Giải pháp:

• Sử dụng hash table để đếm số lượng ký tự trong mẫu.
• Duyệt qua mảng các chuỗi và sử dụng "cửa sổ trượt" để kiểm tra từng dãy con xem có khớp với số lượng ký tự không.

Ví dụ triển khai:

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

# Ví dụ sử dụng:
arr = "cbabadcbbabbcbabaabccbabc"
pattern = "abbc"
print(find_anagram_substring(arr, pattern))  # Kết quả: True

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

Bài tập 1: Tìm phần tử trong mảng chưa sắp xếp

Cho một mảng số và một giá trị mục tiêu. Cần tìm chỉ số của giá trị mục tiêu trong mảng. Sử dụng tìm kiếm tuyến tính.

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 = [10, 20, 30, 40, 50]
target = 30
print(linear_search(arr, target))  # Kết quả: 2

Bài tập 2: Tìm các phần tử trùng lặp trong mảng

Cho một mảng số. Tìm và trả về tất cả các phần tử trùng lặp trong mảng sử dụng hash table.

Ví dụ:

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

# Ví dụ sử dụng:
arr = [1, 3, 5, 3, 7, 9, 1]
print(find_duplicates(arr))  # Kết quả: [3, 1]