Tìm kiếm nhị phân

2.1 Định nghĩa tìm kiếm nhị phân và các khái niệm chính

Tìm kiếm nhị phân là một thuật toán tìm kiếm phần tử trong mảng đã được sắp xếp, hoạt động theo nguyên tắc chia đôi mảng. Thuật toán này hiệu quả hơn nhiều so với tìm kiếm tuyến tính cho các mảng lớn vì nó giảm số lần kiểm tra bằng cách chia đôi mảng ở mỗi lần lặp.

Các khái niệm chính:

• Mảng đã sắp xếp: Tìm kiếm nhị phân chỉ hoạt động trên các mảng đã sắp xếp.
• Chia đôi: Thuật toán so sánh phần tử cần tìm với phần tử ở giữa mảng.
• Chia đôi đệ quy hoặc lặp: Nếu phần tử cần tìm nhỏ hơn phần tử giữa, tiếp tục tìm kiếm trong nửa trái, ngược lại - bên phải.
• Điều kiện kết thúc: Tìm kiếm dừng lại khi tìm thấy phần tử hoặc khi phạm vi tìm kiếm trở nên rỗng.

Quan trọng! Để tìm kiếm nhị phân yêu cầu mảng đã sắp xếp.

Để tìm kiếm nhị phân hoạt động chính xác, dữ liệu đầu vào phải được sắp xếp tăng dần. Đây là yêu cầu chính và duy nhất, vì thuật toán dựa trên thực tế là các phần tử của mảng được sắp xếp. Nhờ đó, nó có thể loại bỏ hiệu quả một nửa số phần tử ở mỗi bước tìm kiếm.

Ví dụ về mảng đã sắp xếp:

sorted_array = [1, 3, 5, 7, 9, 11, 13]

2.2 Triển khai từng bước tìm kiếm nhị phân

Nguyên lý hoạt động của tìm kiếm nhị phân:

1. Khởi tạo: Thiết lập các biên tìm kiếm ban đầu (biên trái và phải của mảng).
2. Chọn phần tử giữa: Tìm chỉ số của phần tử giữa mảng.
3. So sánh: So sánh phần tử giữa với giá trị cần tìm.
4. Cập nhật biên:
   1. Nếu phần tử giữa bằng giá trị cần tìm, trả về chỉ số của nó.
   2. Nếu giá trị cần tìm nhỏ hơn phần tử giữa, cập nhật biên phải.
   3. Nếu lớn hơn - cập nhật biên trái.
5. Lặp lại: Lặp lại các bước 2-4 cho đến khi tìm được phần tử hoặc khi biên trái lớn hơn biên phải.

Thuật toán từng bước:

1. Khởi tạo: Thiết lập left = 0 và right = len(arr) - 1.
2. Tính phần tử giữa: mid = (left + right) // 2
3. So sánh với phần tử mục tiêu:
   1. Nếu arr[mid] == target, trả về mid
   2. Nếu arr[mid] < target, cập nhật left = mid + 1
   3. Nếu arr[mid] > target, cập nhật right = mid - 1
4. Lặp lại: Quay lại bước 2 cho đến khi left <= right
5. Nếu không tìm thấy phần tử: Trả về -1

Triển khai tìm kiếm nhị phân lặp trong Python:

def binary_search(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

# Ví dụ sử dụng:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Phần tử {target} được tìm thấy tại chỉ số {result}")  # Output: Phần tử 7 được tìm thấy tại chỉ số 3

2.3 Độ phức tạp thời gian của tìm kiếm nhị phân O(log n)

Tìm kiếm nhị phân có độ phức tạp thời gian là O(log n), với n là số lượng phần tử trong mảng. Điều này có nghĩa là ở mỗi bước thuật toán chia đôi số lượng phần tử, giúp tăng tốc tìm kiếm đáng kể so với tìm kiếm tuyến tính có độ phức tạp O(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 ở bước đầu tiên, O(1).
• Trường hợp trung bình (Average case): O(log n).
• Trường hợp xấu nhất (Worst case): Phần tử được tìm thấy ở bước cuối hoặc không có, O(log n).

Ví dụ cho phân tích độ phức tạp thời gian:

sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
index = binary_search(sorted_array, target)
print(f"Phần tử {target} được tìm thấy tại chỉ số {index}")  # Output: Phần tử 7 được tìm thấy tại chỉ số 3

# Thuật toán thực hiện 3 bước (log từ 7 phần tử) để tìm phần tử, 
# phù hợp với O(log n)

Biểu diễn đồ họa của độ phức tạp:

Hãy tưởng tượng mảng gồm 16 phần tử.

Giả sử chúng ta tìm phần tử 15, các bước sẽ là:

Bước một. Kiểm tra phần tử giữa (còn lại 8 phần tử).

Bước hai. Kiểm tra phần tử giữa trong nửa còn lại (còn lại 4 phần tử).

Bước ba. Kiểm tra phần tử giữa trong nửa còn lại (còn lại 2 phần tử).

Bước bốn. Kiểm tra phần tử cuối cùng (còn lại 1 phần tử).

Kết quả, thuật toán sẽ thực hiện 4 bước cho mảng gồm 16 phần tử, tương ứng với log cơ số 2 của 16, tức là, log2(16) = 4. Đây chính là độ phức tạp logarithmic O(log n).