Thuật toán tìm kiếm nhị phân trong Python

Khái niệm về thuật toán tìm kiếm nhị phân

Thuật toán tìm kiếm nhị phân là một thuật toán tìm kiếm cơ bản trong lĩnh vực khoa học máy tính. Nó được sử dụng để tìm kiếm một phần tử cụ thể trong một danh sách đã được sắp xếp. Thuật toán này hoạt động bằng cách chia một danh sách đã được sắp xếp thành hai nửa và so sánh phần tử cần tìm với phần tử ở giữa danh sách. Nếu phần tử cần tìm nhỏ hơn phần tử ở giữa danh sách, thuật toán tiếp tục tìm kiếm ở nửa đầu tiên của danh sách. Nếu phần tử cần tìm lớn hơn phần tử ở giữa danh sách, thuật toán tiếp tục tìm kiếm ở nửa thứ hai của danh sách. Thuật toán này tiếp tục lặp lại quá trình này cho đến khi phần tử cần tìm được tìm thấy hoặc danh sách đã bị thu nhỏ xuống còn một phần tử.

Các bước thực hiện thuật toán tìm kiếm nhị phân

Các bước thực hiện thuật toán tìm kiếm nhị phân như sau:

1. Sắp xếp danh sách theo thứ tự tăng dần hoặc giảm dần.
2. Đặt hai biến để đại diện cho giá trị đầu và cuối của danh sách.
3. Tìm giá trị trung bình của danh sách bằng cách lấy tổng giá trị đầu và cuối và chia cho hai.
4. So sánh giá trị cần tìm với giá trị trung bình của danh sách.
5. Nếu giá trị cần tìm bằng giá trị trung bình, trả về vị trí của giá trị đó.
6. Nếu giá trị cần tìm lớn hơn giá trị trung bình, cập nhật giá trị đầu của danh sách bằng giá trị trung bình + 1.
7. Nếu giá trị cần tìm nhỏ hơn giá trị trung bình, cập nhật giá trị cuối của danh sách bằng giá trị trung bình – 1.
8. Lặp lại bước 4 đến bước 7 cho đến khi tìm thấy giá trị cần tìm hoặc danh sách bị thu nhỏ xuống còn một phần tử.

Ví dụ về thuật toán tìm kiếm nhị phân

Cho một danh sách đã được sắp xếp như sau: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19

Giả sử ta muốn tìm kiếm số 11 trong danh sách này bằng thuật toán tìm kiếm nhị phân.

Bước 1: Sắp xếp danh sách theo thứ tự tăng dần: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19

Bước 2: Đặt giá trị đầu của danh sách là 0 và giá trị cuối của danh sách là 9.

Bước 3: Tính giá trị trung bình của danh sách: (0 + 9) / 2 = 4.5. Lấy giá trị này làm vị trí trung tâm trong danh sách.

Bước 4: So sánh giá trị cần tìm (11) với giá trị trung tâm trong danh sách (9). Vì giá trị cần tìm lớn hơn giá trị trung tâm, ta tiếp tục tìm kiếm ở nửa thứ hai của danh sách.

Bước 5: Cập nhật giá trị đầu của danh sách thành giá trị trung tâm + 1: 4.5 + 1 = 5.5. Làm tròn giá trị này thành 6 và đặt làm giá trị đầu của danh sách.

Bước 6: Tính giá trị trung bình của danh sách mới: (6 + 9) / 2 = 7.5. Lấy giá trị này làm vị trí trung tâm trong danh sách mới.

Bước 7: So sánh giá trị cần tìm (11) với giá trị trung tâm trong danh sách mới (11). Vì giá trị cần tìm bằng giá trị trung tâm, ta đã tìm thấy giá trị cần tìm và trả về vị trí của giá trị này trong danh sách (vị trí số 5).

Bước 8: Kết thúc thuật toán.

Đây là một ví dụ về cách thuật toán tìm kiếm nhị phân hoạt động để tìm kiếm một phần tử cụ thể trong một danh sách đã được sắp xếp.

Cài đặt Thuật toán tìm kiếm nhị phân

Cài đặt thuật toán tìm kiếm nhị phân có thể được thực hiện bằng nhiều ngôn ngữ lập trình khác nhau. Dưới đây là một ví dụ về cài đặt thuật toán tìm kiếm nhị phân bằng ngôn ngữ Python:

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0
  
    while low <= high:
        mid = (high + low) // 2

        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
  
    return -1

Bài tập thực hành