Tìm kiếm nhị phân¶

Bài toán và thuật toán tìm kiếm¶

Tương tự bài học trước, ta chỉ xét bài toán đơn giản là tìm kiếm phần tử có tồn tại hay không trên mảng một chiều.

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

Ý tưởng¶

Hãy tưởng tượng tình huống tìm một thuật ngữ bắt đầu bằng chữ cái T trong từ điển. Vì các mục từ trong từ điển đều đã được sắp xếp theo thứ tự bảng chữ cái nên ta không cần lật tìm những trang có chữ cái đầu là A, B hay C, mà chỉ cần lật ngay đến trang có chữ cái đầu là T. Thao tác cứ thế tiếp tục đối với những chữ cái tiếp theo của thuật ngữ cần tìm.

Áp dụng cách trên cho mảng, ta thực hiện hai thao tác:

1. Chia mảng A thành hai mảng con trái và phải.
2. Xét xem k nằm ở mảng con nào.

Lặp lại nhiều lần hai thao tác này cho đến khi tìm thấy k hoặc không còn chia đôi mảng được nữa. Cụ thể như sau:

Ví dụ¶

Lưu đồ thuật toán¶

Trực quan hóa thuật toán¶

Chương trình minh họa¶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# Hàm tìm kiếm nhị phân
def binarySearch(A, k):
    # Khởi tạo mốc trái và mốc phải
    left = 0
    right = len(A) - 1

    # Trong khi left chưa vượt quá right
    # thì xác định vị trí mid và xét k
    while left <= right:

        mid = (left + right) // 2

        if A[mid] == k:
            return mid
        elif A[mid] < k:
            left = mid + 1
        else:
            right = mid - 1

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


# Chương trình chính
if __name__ == '__main__':
    array = [0, 1, 2, 4, 4, 4, 5, 5, 7, 8, 8, 9]
    key = 5

    found_at = binarySearch(array, key)
    if found_at == -1:
        print(f'Không tìm thấy key = {key}')
    else:
        print(f'Tìm thấy key = {key} tại vị trí {found_at}')

Output:

Tìm thấy key = 5 tại vị trí 6

So sánh hai thuật toán tìm kiếm¶

Giống nhau¶

Cả hai thuật toán đều áp dụng cho mảng.

Khác nhau¶

Hai thuật toán có một vài khác biệt chủ yếu sau:

Sơ đồ tóm tắt nội dung¶

Google Colab¶

Các đoạn mã trong bài này được đặt tại Google Colab để bạn có thể thử nghiệm theo cách của riêng mình.

Some English words¶