Các thuật toán tìm kiếm trong Python

NỘI DUNG

Thuật toán tìm kiếm tuần tự (Sequential Search)

Thuật toán tìm kiếm tuần tự (Sequential Search) là một thuật toán cơ bản để tìm kiếm một giá trị trong một danh sách hoặc mảng. Thuật toán này kiểm tra từng phần tử trong danh sách theo thứ tự cho đến khi tìm thấy giá trị cần tìm kiếm hoặc kiểm tra qua toàn bộ danh sách và không tìm thấy giá trị đó.

Quá trình của thuật toán tìm kiếm tuần tự bao gồm các bước sau:

Duyệt qua từng phần tử của danh sách theo thứ tự, bắt đầu từ phần tử đầu tiên.
So sánh phần tử hiện tại với giá trị cần tìm kiếm.
Nếu tìm thấy giá trị cần tìm kiếm, trả về chỉ số của phần tử đó.
Nếu đã duyệt qua toàn bộ danh sách mà không tìm thấy giá trị, trả về -1 để thể hiện rằng giá trị không tồn tại trong danh sách.

Thuật toán tìm kiếm tuần tự hiệu quả cho các danh sách nhỏ hoặc khi bạn cần tìm kiếm một phần tử cụ thể trong danh sách không được sắp xếp. Tuy nhiên, đối với danh sách lớn, thuật toán tìm kiếm tuần tự có độ phức tạp thời gian là O(n), với n là số phần tử trong danh sách, nên không phải lúc nào cũng là lựa chọn tốt nhất.

Code tham khảo:

def sequential_search(arr, target):
    for i, item in enumerate(arr):
        if item == target:
            return i  # Trả về chỉ số của phần tử nếu tìm thấy
    return -1  # Trả về -1 nếu không tìm thấy

# Ví dụ sử dụng:
arr = [64, 34, 25, 12, 22, 11, 90]
target = 25
result = sequential_search(arr, target)
if result != -1:
    print(f"{target} được tìm thấy tại vị trí {result}")
else:
    print(f"{target} không tồn tại trong danh sách")

Thuật toán tìm kiếm nhị phân (Binary Search)

Thuật toán tìm kiếm nhị phân (Binary Search) là một thuật toán tìm kiếm hiệu quả được sử dụng để tìm kiếm một giá trị trong một danh sách đã sắp xếp. Thuật toán này hoạt động bằng cách chia đôi danh sách tại một điểm giữa và so sánh giá trị tại điểm đó với giá trị cần tìm kiếm. Nếu giá trị tại điểm đó bằng giá trị cần tìm kiếm, thuật toán kết thúc. Nếu không, nó sẽ tiếp tục tìm kiếm trong một phần của danh sách dựa trên kết quả so sánh và loại bỏ nửa còn lại của danh sách.

Quá trình của thuật toán tìm kiếm nhị phân bao gồm các bước sau:

Xác định chỉ số bắt đầu (left) và chỉ số kết thúc (right) của danh sách.
Tính điểm giữa của danh sách (mid) bằng cách lấy trung bình của left và right.
So sánh giá trị tại điểm giữa (arr[mid]) với giá trị cần tìm kiếm.
Nếu tìm thấy giá trị, trả về chỉ số của phần tử.
Nếu giá trị tại điểm giữa lớn hơn giá trị cần tìm kiếm, thuật toán tiếp tục tìm kiếm trong nửa trái của danh sách (cập nhật right).
Nếu giá trị tại điểm giữa nhỏ hơn giá trị cần tìm kiếm, thuật toán tiếp tục tìm kiếm trong nửa phải của danh sách (cập nhật left).
Lặp lại quá trình cho đến khi tìm thấy giá trị hoặc left > right. Nếu không tìm thấy, trả về -1.

Thuật toán tìm kiếm nhị phân có độ phức tạp thời gian là O(log n), nơi n là số phần tử trong danh sách. Điều này làm cho nó rất hiệu quả và phù hợp cho các danh sách lớn. Tuy nhiên, danh sách phải được sắp xếp trước khi áp dụng thuật toán tìm kiếm nhị phân.

Code tham khảo:

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2  # Tính điểm giữa

        if arr[mid] == target:
            return mid  # Trả về chỉ số của phần tử nếu tìm thấy
        elif arr[mid] < target:
            left = mid + 1  # Tìm kiếm trong nửa phải của danh sách
        else:
            right = mid - 1  # Tìm kiếm trong nửa trái của dsách

    return -1  # Trả về -1 nếu không tìm thấy

# Ví dụ sử dụng:
arr = [11, 12, 22, 25, 34, 64, 90]
target = 25
result = binary_search(arr, target)
if result != -1:
    print(f"{target} được tìm thấy tại vị trí {result}")
else:
    print(f"{target} không tồn tại trong danh sách")

Sử dụng các hàm tìm kiếm có sẵn trong Python

Python cung cấp một số hàm và phương thức tìm kiếm có sẵn để giúp bạn tìm kiếm giá trị trong danh sách hoặc dãy dữ liệu. Dưới đây là một số trong những hàm và phương thức này:

Phương thức list.index()

Phương thức index() được sử dụng để tìm chỉ số của một giá trị cụ thể trong danh sách. Nếu giá trị không tồn tại trong danh sách, phương thức này sẽ ném ra một ngoại lệ ValueError.

arr = [64, 34, 25, 12, 22, 11, 90]
target = 25
index = arr.index(target)
print(f"{target} được tìm thấy tại vị trí {index}")

Toán tử in operator

Toán tử in được sử dụng để kiểm tra xem một giá trị có tồn tại trong danh sách hay không. Nó trả về một giá trị boolean (True nếu tồn tại và False nếu không tồn tại).

arr = [64, 34, 25, 12, 22, 11, 90]
target = 25
if target in arr:
    print(f"{target} tồn tại trong danh sách")
else:
    print(f"{target} không tồn tại trong danh sách")

Phương thức count()

Phương thức count() được sử dụng để đếm số lần một giá trị xuất hiện trong danh sách.

arr = [64, 34, 25, 25, 22, 11, 90]
target = 25
count = arr.count(target)
print(f"{target} xuất hiện {count} lần trong danh sách")

Hàm any()

Hàm any() được sử dụng để kiểm tra xem ít nhất một phần tử trong danh sách thỏa mãn một điều kiện cụ thể.

arr = [64, 34, 25, 12, 22, 11, 90]
condition = any(x > 50 for x in arr)
print(f"Có ít nhất một phần tử lớn hơn 50: {condition}")

Hàm all()

Hàm all() được sử dụng để kiểm tra xem tất cả các phần tử trong danh sách đều thỏa mãn một điều kiện cụ thể.

arr = [64, 34, 25, 12, 22, 11, 90]
condition = all(x > 10 for x in arr)
print(f"Tất cả các phần tử lớn hơn 10: {condition}")

Lưu ý: Một số phương thức và hàm trên có thể chỉ hoạt động với danh sách đã sắp xếp hoặc không sắp xếp tùy thuộc vào yêu cầu cụ thể của bạn.

Lập trình Python