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

1.1 Định nghĩa tìm kiếm tuyến tính

Tìm kiếm tuyến tính (còn được gọi là tìm kiếm tuần tự) là một thuật toán để tìm kiếm một phần tử trong danh sách hoặc mảng bằng cách kiểm tra tuần tự từng phần tử cho đến khi tìm thấy một phần tử khớp hoặc kiểm tra hết tất cả các phần tử. Đây là thuật toán tìm kiếm đơn giản nhất, không yêu cầu sắp xếp dữ liệu trước.

Nguyên tắc cơ bản:

• Kiểm tra tuần tự: Thuật toán đi qua từng phần tử của mảng hoặc danh sách, so sánh nó với giá trị cần tìm.
• Dừng tìm kiếm: Tìm kiếm dừng lại khi tìm thấy một phần tử khớp với giá trị cần tìm hoặc khi tất cả các phần tử đã được kiểm tra.
• Không yêu cầu sắp xếp: Tìm kiếm tuyến tính có thể áp dụng cho dữ liệu không được sắp xếp.
• Ứng dụng: Tìm kiếm tuyến tính có thể áp dụng cho bất kỳ cấu trúc dữ liệu nào hỗ trợ lặp lại, bao gồm danh sách và mảng.

Tìm kiếm tuyến tính có độ phức tạp thời gian là O(n), ở đây n là số lượng phần tử trong mảng hoặc danh sách. Trong trường hợp xấu nhất, thuật toán cần kiểm tra tất cả n phần tử để tìm giá trị cần tìm hoặc xác định sự vắng mặt của nó.

Phân tích độ phức tạp thời gian:

• Trường hợp tốt nhất (Best case): Phần tử được tìm thấy ở vị trí đầu tiên, O(1).
• Trường hợp trung bình (Average case): Phần tử được tìm thấy ở khoảng giữa, O(n/2), tương đương với O(n).
• Trường hợp xấu nhất (Worst case): Phần tử được tìm thấy ở vị trí cuối cùng hoặc không tồn tại, O(n).

1.2 Triển khai từng bước tìm kiếm tuyến tính

Các bước tìm kiếm tuyến tính:

• Khởi tạo: Đặt chỉ số bắt đầu cho việc tìm kiếm (thường là chỉ số 0).
• Kiểm tra tuần tự: Kiểm tra từng phần tử của danh sách hoặc mảng để tìm sự khớp với giá trị cần tìm.
• Điều kiện kết thúc: Nếu tìm thấy phần tử, trả lại chỉ số của nó. Nếu tất cả các phần tử đã được kiểm tra và không tìm thấy giá trị cần tìm, trả lại giá trị đặc biệt (thường là -1 hoặc None).

Triển khai tìm kiếm tuyến tính trong Python:

def linear_search(arr, target):
    # Duyệt từng phần tử của mảng
    for index, element in enumerate(arr):
        # Nếu phần tử hiện tại bằng với giá trị cần tìm, trả về chỉ số của nó
        if element == target:
            return index
    # Nếu không tìm thấy phần tử, trả về -1
    return -1

Giải thích từng bước triển khai:

• Khởi tạo vòng lặp: Sử dụng vòng lặp for với hàm enumerate, trả về chỉ số và phần tử của mảng trong từng lần lặp.
• So sánh: Trong mỗi lần lặp, so sánh phần tử hiện tại với giá trị cần tìm (target).
• Trả về chỉ số: Nếu phần tử hiện tại bằng với giá trị cần tìm, trả về chỉ số của nó.
• Trả về -1: Nếu vòng lặp kết thúc và không tìm thấy phần tử cần tìm, trả về -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 tại chỉ số {result}")  # Kết quả: Phần tử 7 được tìm thấy tại 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 tại chỉ số {result}")  # Kết quả: Phần tử 5 được tìm thấy tại chỉ số -1

1.3 Ví dụ các bài toán giải quyết bằng tìm kiếm tuyến tính

Tìm kiếm tuyến tính được sử dụng để giải quyết nhiều bài toán liên quan đến việc tìm kiếm phần tử trong các bộ sưu tập dữ liệu. Dưới đây là một vài ví dụ:

Bài toán 1: Tìm kiếm phần tử trong mảng

Cần tìm một số cho trước trong mảng số.

Ví dụ:

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

arr = [10, 23, 45, 70, 11, 15]
target = 70
index = linear_search(arr, target)
print(f"Phần tử {target} được tìm thấy tại chỉ số {index}")  # Kết quả: Phần tử 70 được tìm thấy tại chỉ số 3

Bài toán 2: Kiểm tra sự tồn tại của phần tử trong danh sách

Cần kiểm tra xem liệu giá trị cho trước có tồn tại trong danh sách chuỗi.

Ví dụ:

def linear_search(arr, target):
    for element in arr:
        if element == target:
            return True
    return False

words = ["apple", "banana", "cherry", "date"]
target = "cherry"
found = linear_search(words, target)
print(f"Phần tử {target} {'được tìm thấy' if found else 'không tìm thấy'}")  # Kết quả: Phần tử cherry được tìm thấy

Bài toán 3: Tìm kiếm giá trị nhỏ nhất hoặc lớn nhất

Cần tìm giá trị nhỏ nhất hoặc lớn nhất trong danh sách.

Ví dụ:

def find_min(arr):
    if not arr:
        return None
    min_val = arr[0]
    for element in arr:
        if element < min_val:
            min_val = element
    return min_val

arr = [34, 17, 23, 2, 45, 13]
min_value = find_min(arr)
print(f"Giá trị nhỏ nhất: {min_value}")  # Kết quả: Giá trị nhỏ nhất: 2

Bài toán 4: Tìm kiếm lần xuất hiện đầu tiên

Tìm lần xuất hiện đầu tiên của phần tử cho trước trong danh sách.

Ví dụ:

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

arr = [4, 2, 7, 1, 9, 3, 2]
target = 2
index = find_first_occurrence(arr, target)
print(f"Lần xuất hiện đầu tiên của {target} tại chỉ số {index}")  # Kết quả: Lần xuất hiện đầu tiên của 2 tại chỉ số 1

Bài toán 5: Đếm số lần xuất hiện

Đếm số lần xuất hiện của phần tử cho trước trong danh sách.

Ví dụ:

def count_occurrences(arr, target):
    count = 0
    for element in arr:
        if element == target:
            count += 1
    return count

arr = [4, 2, 7, 2, 9, 3, 2]
target = 2
count = count_occurrences(arr, target)
print(f"Phần tử {target} xuất hiện {count} lần")  # Kết quả: Phần tử 2 xuất hiện 3 lần