Tìm kiếm nhị phân đệ quy

3.1 Nguyên tắc hoạt động của tìm kiếm nhị phân đệ quy

Tìm kiếm nhị phân là một thuật toán để tìm một phần tử trong một mảng đã sắp xếp, hoạt động theo nguyên tắc "chia để trị". Nó so sánh phần tử cần tìm với phần tử ở giữa mảng và quyết định tìm kiếm tiếp theo ở nửa nào của mảng. Tìm kiếm nhị phân đệ quy lặp lại quá trình này bằng cách tự gọi chính nó với các giới hạn mảng được cập nhật.

Các bước của thuật toán:

1. So sánh phần tử cần tìm với phần tử ở giữa mảng.
2. Nếu phần tử ở giữa trùng với phần tử cần tìm, trả về chỉ số của nó.
3. Nếu phần tử cần tìm nhỏ hơn, lặp lại tìm kiếm ở nửa trái của mảng.
4. Nếu phần tử cần tìm lớn hơn, lặp lại tìm kiếm ở nửa phải của mảng.
5. Lặp lại quá trình cho đến khi tìm thấy phần tử hoặc hết mảng.

Thực hiện tìm kiếm nhị phân đệ quy

Ví dụ với Python:

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1  # Trường hợp cơ bản: không tìm thấy phần tử
            
    mid = (left + right) // 2  # Tìm phần tử giữa mảng
            
    if arr[mid] == target:
        return mid  # Trường hợp cơ bản: tìm thấy phần tử
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)  # Tìm kiếm ở nửa phải
    else:
        return binary_search_recursive(arr, target, left, mid - 1)  # Tìm kiếm ở nửa trái
        
# Ví dụ sử dụng:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search_recursive(arr, target, 0, len(arr) - 1)
print(f"Phần tử được tìm thấy ở vị trí: {result}")  # Sẽ in ra: Phần tử được tìm thấy ở vị trí: 6
        

3.2 So sánh với tìm kiếm nhị phân lặp

Tìm kiếm nhị phân lặp:

def binary_search_iterative(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  # Không tìm thấy phần tử
        
# Ví dụ sử dụng:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search_iterative(arr, target)
print(f"Phần tử được tìm thấy ở vị trí: {result}")  # Sẽ in ra: Phần tử được tìm thấy ở vị trí: 6
        

So sánh:

Sự đơn giản trong triển khai:

• Thuật toán đệ quy thường đơn giản và ngắn gọn hơn, nhưng yêu cầu hiểu biết về các cuộc gọi đệ quy.
• Thuật toán lặp sử dụng vòng lặp, có thể dễ hiểu hơn cho những người lập trình mới bắt đầu.

Bộ nhớ:

• Thuật toán đệ quy sử dụng ngăn xếp gọi, có thể dẫn đến tăng sử dụng bộ nhớ với các mảng lớn.
• Thuật toán lặp sử dụng một lượng bộ nhớ cố định, làm cho nó hiệu quả hơn về sử dụng bộ nhớ.

Hiệu suất:

• Cả hai thuật toán có độ phức tạp thời gian là O(log n).
• Thuật toán đệ quy có thể chậm hơn do chi phí của các cuộc gọi đệ quy, đặc biệt nếu độ sâu đệ quy lớn.

3.3 Ví dụ về bài toán cho tìm kiếm nhị phân đệ quy

Tìm kiếm nhị phân đệ quy là một thuật toán mạnh mẽ giúp nhanh chóng tìm thấy các phần tử trong các mảng đã sắp xếp. Nó dựa trên nguyên tắc "chia để trị" và sử dụng đệ quy để chia bài toán thành những bài toán con nhỏ hơn.

So sánh giữa cách tiếp cận đệ quy và lặp cho thấy mỗi cách đều có ưu nhược điểm riêng tùy vào bài toán cụ thể. Hiểu được các thuật toán này và cách áp dụng của chúng giúp bạn giải quyết các bài toán tìm kiếm trong lập trình một cách hiệu quả.

Ví dụ, như:

Tìm kiếm phần tử trong mảng đã sắp xếp:

Tìm kiếm một phần tử cụ thể trong một mảng số, ví dụ như đánh giá bài kiểm tra, tìm kiếm trong cơ sở dữ liệu dựa trên các khóa đã sắp xếp và tương tự.

Kiểm tra sự hiện diện của phần tử:

Kiểm tra xem một giá trị cụ thể có xuất hiện trong danh sách người dùng được phép, danh sách định danh và tương tự.

Tìm kiếm giá trị gần nhất:

Tìm phần tử gần nhất với giá trị cho trước trong mảng, ví dụ như khi tìm cửa hàng, trạm gần nhất và tương tự.

Tối ưu hóa:

Giải quyết các bài toán cần tìm kiếm giá trị tối ưu trong mảng đã sắp xếp, ví dụ như tìm điểm tối thiểu hoặc tối đa trong các hàm.