Thuật toán đệ quy nhị phân (Binary recursive algorithm)

Thuật toán đệ quy nhị phân (Binary recursive algorithm) là một thuật toán sắp xếp đặc biệt được sử dụng để tìm kiếm các giá trị trong một danh sách đã sắp xếp.

Cách thức hoạt động của thuật toán này như sau:

1. Tìm giá trị trung bình của danh sách đã sắp xếp.
2. So sánh giá trị trung bình với giá trị cần tìm.
3. Nếu giá trị trung bình bằng giá trị cần tìm, trả về vị trí của giá trị đó trong danh sách.
4. Nếu giá trị trung bình lớn hơn giá trị cần tìm, tìm kiếm trong nửa đầu tiên của danh sách.
5. Nếu giá trị trung bình nhỏ hơn giá trị cần tìm, tìm kiếm trong nửa thứ hai của danh sách.
6. Lặp lại quá trình trên cho đến khi tìm thấy giá trị cần tìm hoặc không còn phần tử nào để tìm kiếm.

Độ phức tạp của thuật toán đệ quy nhị phân (Binary recursive algorithm) là O(log n), tốc độ nhanh hơn so với các thuật toán tìm kiếm khác.

Dưới đây là đoạn code Python mẫu để tìm kiếm một phần tử trong danh sách sử dụng thuật toán đệ quy nhị phân:

def binary_search(arr, low, high, x):
    if high >= low:
        mid = (high + low) // 2

        if arr[mid] == x:
            return mid

        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)

        else:
            return binary_search(arr, mid + 1, high, x)

    else:
        return -1

Ví dụ: Cho danh sách [11, 12, 22, 25, 64] và tìm kiếm phần tử có giá trị là 25. Sử dụng thuật toán đệ quy nhị phân, ta có kết quả là 3.

arr = [11, 12, 22, 25, 64]
x = 25
result = binary_search(arr, 0, len(arr)-1, x)
print(result) # Kết quả là 3